Finding the next palindrome of a number string

Here is the 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

Here is my code:

```
// I know it is bad practice to not cater for erroneous input,
// however for the purpose of the execise it is omitted
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.lang.Exception;
import java.math.BigInteger;

public class Main
{
public static void main(String [] args){
try{
Main instance = new Main(); // create an instance to access non-static
// variables

// Use java.util.Scanner to scan the get the input and initialise the
// variable
Scanner sc=null;

BufferedReader r = new BufferedReader(new InputStreamReader(System.in));

String input = "";

int numberOfTests = 0;

String k; // declare any other variables here

if((input = r.readLine()) != null){
sc = new Scanner(input);
numberOfTests = sc.nextInt();
}

for (int i = 0; i l then offest needs updating
if(right > left){
// update and replace
right = left;
insert = Integer.toString(right);

theNumber.replace(rightPos, rightPos + 1, insert);

offset++; if (offset ==

Among other things:

-
Knowing the right-side chars has exactly one purpose: it tells you whether the number you're making (when palindromized) can be returned as is, or whether you have to find the "next" one. So have a flag needsBump that starts out true. Before you copy each char from the left side to the right, set the flag to (left

-
Once you've determined you need to bump the number, you only have to start at the middle digit(s) and work your way out til you no longer have to carry. If you're at the end of the number and still have to carry, prepend and append a '1'.

-
You're doing way too much parsing and stringifying. Integer.toString(...), String.valueOf(...), etc create a new string each time -- which in String.valueOf's case, you're just throwing away as soon as you parse. You're talking about potentially millions of strings. Stop trying to parse the numbers, and just work with them as chars. You should see a pretty big speed boost.



• StringBuffer and StringBuilder both have a setCharAt method, which you should be using (considering your "strings" always consist of a single char).






• offset++; if (offset == 10) offset = 0; becomes if (++offset > '9') offset = '0';, for example.






• Integer.parseInt(String.valueOf(theNumber.charAt(leftPos))) becomes just theNumber.charAt(leftPos)






• You may be able to get rid of the string buffer/builder altogether and work with a regular old char[]. All of your operations will be in terms of chars, and you shouldn't have any insertion to do in the general case -- except if K == 99...99, in which case you need to return 100...001. But that's easy enough to do with + when you have to.




-
If you stick with string buffers, StringBuilder` is generally faster, and should be preferred if you don't require synchronization (which you don't).

Style issues:

• Declaring every variable you'll ever use at the top of the function is a very Pascal way to do things. Prefer declaring variables as close as possible to their first use. It reduces scope, and along with that, decreases the number of things someone reading your code has to worry about at one time.

StackExchange Code Review Q#5671, answer score: 6