The challenge

Reverse Number is a number which is the same when reversed.

For example, the first 20 Reverse Numbers are:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101

Task

  • You need to return the nth reverse number. (Assume that reverse numbers start from 0 as shown in the example.)

Notes

  • 1 < n <= 100000000000

The solution in Java

Option 1:

import java.math.BigInteger;

public class Palindrome {

    private static int length = 0;

    public static BigInteger findReverseNumber(long n) {
        if (n == 1) {
            return BigInteger.ZERO;
        }
        length = 0;
        String remainder = findLengthAndRemainder(n - 1);
        while (remainder.length() < (length + 1) / 2) {
            remainder = "0" + remainder;
        }
        StringBuilder result = new StringBuilder();
        if (remainder.matches("\\d0*")) {
            result.append(remainder.charAt(0));
            result.append("9".repeat(remainder.length() - 1));
        } else {
            result.append(Integer.parseInt(remainder.substring(0, 1)) + 1);
            String value = String.valueOf(new BigInteger(remainder.substring(1)).subtract(BigInteger.ONE));
            while (value.length() < remainder.length() - 1) {
                value = "0" + value;
            }
            result.append(value);
        }
        String firstHalf = result.toString();
        String secondHalf = result.reverse().substring(length % 2);
        return new BigInteger(firstHalf + secondHalf);
    }

    private static String findLengthAndRemainder(long number) {
        long subtract = 9;
        while (number > 0) {
            length++;
            number -= subtract;
            if (number <= 0) {
                break;
            }
            length++;
            number -= subtract;
            if (number > 0) {
                subtract *= 10;
            }
        }
        number += subtract;
        return String.valueOf(number);
    }

}

Test cases to validate our solution

import org.junit.jupiter.api.Test;

import java.math.BigInteger;

import static org.junit.jupiter.api.Assertions.assertEquals;

class PalindromeTest {

    @Test
    void testFixed() {
        assertEquals(new BigInteger("0"), Palindrome.findReverseNumber(1));
        assertEquals(new BigInteger("1"), Palindrome.findReverseNumber(2));
        assertEquals(new BigInteger("9"), Palindrome.findReverseNumber(10));
        assertEquals(new BigInteger("909"), Palindrome.findReverseNumber(100));
        assertEquals(new BigInteger("900000000000000000009"), Palindrome.findReverseNumber(100000000000L));
    }

}