# A better algorithm to find the next palindrome of a number string

Firstly 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
``````

Secondly 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.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;

String input = "";

int numberOfTests = 0;

String k; // declare any other variables here

sc = new Scanner(input);
numberOfTests = sc.nextInt();
}

for (int i = 0; i < numberOfTests; i++){
sc = new Scanner(input);
k=sc.next(); // initialise the remainder of the variables sc.next()
instance.palindrome(k);
} //if
}// for
}// try

catch (Exception e)
{
e.printStackTrace();
}
}// main

public void palindrome(String number){

StringBuffer theNumber = new StringBuffer(number);
int length = theNumber.length();
int left, right, leftPos, rightPos;
// if incresing a value to more than 9 the value to left (offset) need incrementing
int offset, offsetPos;
boolean offsetUpdated;
// To update the string with new values
String insert;
boolean hasAltered = false;

for(int i = 0; i < length/2; i++){
leftPos = i;
rightPos = (length-1) - i;
offsetPos = rightPos -1; offsetUpdated = false;

// set values at opposite indices and offset
left = Integer.parseInt(String.valueOf(theNumber.charAt(leftPos)));
right = Integer.parseInt(String.valueOf(theNumber.charAt(rightPos)));
offset = Integer.parseInt(String.valueOf(theNumber.charAt(offsetPos)));

if(left != right){
// if r > 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 == 10) offset = 0;
insert = Integer.toString(offset);

theNumber.replace(offsetPos, offsetPos + 1, insert);
offsetUpdated = true;

// then we need to update the value to left again
while (offset == 0 && offsetUpdated){
offsetPos--;
offset =
Integer.parseInt(String.valueOf(theNumber.charAt(offsetPos)));
offset++; if (offset == 10) offset = 0;
// replace
insert = Integer.toString(offset);
theNumber.replace(offsetPos, offsetPos + 1, insert);
}
// finally incase right and offset are the two middle values
left = Integer.parseInt(String.valueOf(theNumber.charAt(leftPos)));
if (right != left){
right = left;
insert = Integer.toString(right);
theNumber.replace(rightPos, rightPos + 1, insert);
}
}// if r > l
else
// update and replace
right = left;
insert = Integer.toString(right);
theNumber.replace(rightPos, rightPos + 1, insert);
}// if l != r
}// for i
System.out.println(theNumber.toString());
}// palindrome
}
``````

Finally my explanation and question.

`````` My code compares either end and then moves in
if left and right are not equal
if right is greater than left
(increasing right past 9 should increase the digit
to its left i.e 09 ---- > 10) and continue to do
so if require as for 89999, increasing the right
most 9 makes the value 90000

before updating my string we check that the right
and left are equal, because in the middle e.g 78849887
we set the 9 --> 4 and increase 4 --> 5, so we must cater for this.
``````

The problem is from spoj.pl an online judge system. My code works for all the test can provide but when I submit it, I get a time limit exceeded error and my answer is not accepted.

Does anyone have any suggestions as to how I can improve my algorithm. While writing this question I thought that instead of my `while (offset == 0 && offsetUpdated)` loop I could use a `boolean` to to make sure I increment the `offset` on my next [i] iteration. Confirmation of my change or any suggestion would be appreciated, also let me know if I need to make my question clearer.

-
You could significantly speed it up if you convert the digit to an integer by hand instead of parsing it. e.g. `'5' - '0' == 5`. –  Jeff Mercado Oct 28 '11 at 21:12
Could speed it up even more if you stopped trying to think of it as an integer at all. –  cHao Oct 28 '11 at 23:53

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<right || (needsBump && left==right))`. (Don't do any incrementing yet; do that separately once you've determined you need to. Just copy chars.) Once you've gotten to the middle, `needsBump` will indicate whether you need to bump the number up. (The most significant digits to determine whether you need to bump are the middle ones. If the left one is bigger than the right, then copying from left to right increases the number (making it unnecessary to bump). If it's smaller, then copying will decrease the resulting number, making it necessary to bump -- however, even the smallest change to the least significant digit of the left side has more value than the entirety of the right side of the number. If the left and right digits are equal, then the last decision made stands.)

• 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.
-
doesn't `theNumber.charAt(leftPos)` return ath ASCII and not the integer value? –  Mead3000 Oct 29 '11 at 9:53
@Mead3000: Yes. But guess what? You don't need the integer value. The only thing you're going to do with the char is bump it up by one, and if it's greater than '9', set it to '0' and repeat with the char to the left. None of this requires that you know the integer value of the char. If you insist on integer values, though, either `Character.digit(ch, 10)` or `ch - '0'` will give you that. In either case, you don't need to stringify or parse. –  cHao Oct 29 '11 at 13:20
Ah yeah, I understand now thanks a lot. –  Mead3000 Oct 29 '11 at 13:29

Actually for any Programming Contest Java is slower(very little) than C/C++. If you don't believe you can see it yourself. So I have seen many people using own defined methods to read and write inputs and outputs respectively. You can get the idea from a post in CR.

Now come to the code I didn't benchmark your palindrome code(sorry for that) but at first glance it's very big and I'm sure it's also hard to maintain. So as a Java programmer this should be your first concern.

Enough talk let's write the code

``````import java.io.BufferedReader;
import java.io.IOException;

class NextPalNo {
public static void main (String[] args) throws IOException {

// we know 1 to 9 all are palindrome numbers
if(i < 9)
System.out.println(i+1);

else {
while(true) {
i += 1;
if(isPalindrome(i))
break;
}
System.out.println(i);
}
br.close();
}

public static boolean isPalindrome(int i) {
String s = String.valueOf(i);
// easy way to see if a number is palindrome or not ;)
return new StringBuilder(s).reverse().toString().equals(s);
}
}
``````
-