Handling large numbers

Question

I have this problem:

A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros. Input

The first line contains integer t, the number of test cases. Integers K are given in the next t lines. Output

For each K, output the smallest palindrome larger than K. Example

Input:

2
808
2133

Output:

818
2222

My code converts the input to a string and evaluates either end of the string making adjustments accordingly and moves inwards. However, the problem requires that it can take values up to 10^6 digits long, if I try to parse large numbers I get a number format exception i.e.

Integer.parseInt(LARGENUMBER);

or

Long.parseInt(LARGENUMBER);

and LARGENUMBER is out of range. can anyone think of a work around or how to handle such large numbers?

Answer 1

You could probably use the BigInteger class to handle large integers like this.

However, I wouldn't count on it being efficient at such massive sizes. Because it still uses O(n^2) algorithms for multiplication and conversions.

Answer 2

Think of your steps that you do now. Do you see something that seems a little superfluous since you're converting the number to a string to process it?

Answer 3

While this problem talks about integers, its doing so only to restrict the input and output characters and format. This is really a string operations question with careful selection. Since this is the case, you really don't need to actually read the input in as integers, only strings.

This will make validating the palindrome simple. The only thing you should need to work out is choosing the next higher one.