Finding the next palindrome of a number string

Question

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 < numberOfTests; i++){
 if((input = r.readLine()) != null){
 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.

• Jeff Mercado: 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.
• cHao: Could speed it up even more if you stopped trying to think of it as an integer at all.

Answer 1

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.

• Mead3000: doesn't theNumber.charAt(leftPos) return ath ASCII and not the integer value?
• cHao: @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.

Answer 2

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.InputStreamReader;
import java.io.IOException;
class NextPalNo {
 public static void main (String[] args) throws IOException {
 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 int i = Integer.parseInt(br.readLine());
 // 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);
 }
}