Finding the next palindrome for the given number

Problem

Given a number, find the next smallest palindrome larger than this number.

Example

For example, if the input number is “2 3 5 4 5″, the output should be “2 3 6 3 2″. And if the input number is “9 9 9″, the output should be “1 0 0 1″.
The input is assumed to be an array. Every entry in array represents a digit in input number. Let the array be ‘num[]‘ and size of array be ‘n’
There can be three different types of inputs that need to be handled separately.

1. The input number is palindrome and has all 9s. For example “9 9 9″. Output should be “1 0 0 1″
2. The input number is not palindrome. For example “1 2 3 4″. Output should be “1 3 3 1″
3. The input number is palindrome and doesn’t have all 9s. For example “1 2 2 1″. Output should be “1 3 3 1″.

Solution

Method 1 - Start from center of number and increment MSB part
Solution for input type 1 is easy. The output contains n + 1 digits where the corner digits are 1, and all digits between corner digits are 0.
Now let us first talk about input type 2 and 3. How to convert a given number to a greater palindrome?

Basic Algo
Lets follow following algorithm:

1. Find the decimal representation of the input number ("2133").
2. Split it into the left half and right half ("21", "33"); If the number of digits is odd, ignore the center element, of course it will be needed later.
3. Now, take 2 indices left and right, such that left is at the last of the left half, and right is at the the start of right half.
   We will decrement left to start of left half and increment right to 2nd half.
   Compare the last digit in the left half and the first digit in the right half.
   a. If the right is greater than the left, increment the left and stop. ("22")
   b. If the right is less than the left, stop.
   c. If the right is equal to the left, repeat step 3 with the second-last digit in the left and the second digit in the right (and so on).
4. If you run out of the iterators in the left and half, i.e.left and half and right half are equal, incrment the left half. ( In case of odd bit number, just increment the center number.)
5. Take the left half and append the left half reversed. That's your next largest palindrome. ("2222")

Example of above algo

1.    1234567887654322
2.    12345678   87654322
3.    12345678   87654322
             ^   ^         equal
3.    12345678   87654322
            ^     ^        equal
3.    12345678   87654322
           ^       ^       equal
3.    12345678   87654322
          ^         ^      equal
3.    12345678   87654322
         ^           ^     equal
3.    12345678   87654322
        ^             ^    equal
3.    12345678   87654322
       ^               ^   equal
3.    12345678   87654322
      ^                 ^  greater than, so increment the left

3.    12345679

4.    1234567997654321  answer

Method 2 - Breaking number in 2 halfs and comparing them as numbers
Here is another algo:

1. Break the number into 2 halfs "2133" = "21","33"
2. Now if first half is greater than 2nd half AND first half is same size as 2nd half AND reverse(first) is greater than 2nd half, then nextPalindrome = first + reverse(first), otherwise go to step 3.  Example 783322 = 783 + 387 = 783387. However 2133 wont hold. Nor will 1001, as first = 10, and last = 01 = 1
3. Increment the first half by 1,
   first = first+1
   nextPalindrome = first + reverse(first)
   Example 2133, first = 21, first+1 = 22, Now concat first and reverse first = 2222

Program
Here is the java code

private static int getLengthOfInt(int x)
{
 int length = String.valueOf(x).length();
 return length;
}
public static int getNextPalindrome(int number){
 List<Integer> digitsArray = new ArrayList<Integer>();
 List<Integer> digitsHalfArray = new ArrayList<Integer>();
 digitsArray=NumberToDigits(number);       

 //if even number of digits, then consider middle two numbers as the middle
 //convert digits from left to mid and mid-1 to a single number
 //convert digits from right to mid  to a single number
 int count = digitsArray.size();
 out.println(count);
 int mid = count / 2;
 int last = 0, first = 0,middle=0,i=0,j=0;
 Boolean odd = false;
 //if number of digits is even
 if (count % 2 == 0)
 {                
  last = DigitsToNumber(digitsArray, mid, count - 1);
  first = DigitsToNumber(digitsArray, 0, mid - 1);
  i = mid;
  j = mid - 1;
 }
 else
 {
  odd=true;
  middle = digitsArray.get(mid);
  first = DigitsToNumber(digitsArray, 0, mid - 1);
  last = DigitsToNumber(digitsArray, mid + 1, count - 1); 
  //mid is increased to adjust the midddle number in odd number of digits case
  mid++;
  i = mid;
  j = mid - 2;
 }
 out.println(first);
 out.println(last);
 //also see if the size, first!=last in size for 1001
 if (first > last && getLengthOfInt(first)==getLengthOfInt(last))
 {

  for (; i < count; ++i, j--)
  {
   digitsArray.add(i,digitsArray.get(j));
  }
  out.println(DigitsToNumber(digitsArray,0, count - 1));

 }
 else
 {
  //including the middle digit also
  first = DigitsToNumber(digitsArray, 0, mid-1);
  //adding 1 to middle value
  first = first + 1;
  digitsHalfArray = NumberToDigits(first);
  digitsArray=digitsHalfArray;
  int dHalfCount=digitsArray.size();

  //adjustment for number with odd number of digits
  if(odd==true)
  {
   mid--;
   odd=false;
  }
  System.out.println(dHalfCount);
  for (int k = mid-1; k >=0; --k)
  {
   digitsArray.add(dHalfCount++, digitsHalfArray.get(k));
  }
  out.println("Nearest Palindrome = " +DigitsToNumber(digitsArray, 0, digitsArray.size()-1));
 }
 return DigitsToNumber(digitsArray,0,digitsArray.size()-1);

}
private static List<Integer> NumberToDigits(int number)
{
 List<Integer> digitsArray = new ArrayList<Integer>();
 int[] tempArray = new int[51];
 int tempCount = 0;           
 while (number > 0)
 {
  tempArray[tempCount++] = number % 10;
  number = number / 10;
 }
 //reverse the digits and store in a list
 for (int i = tempCount-1; i >= 0; --i)
 {
  digitsArray.add(tempArray[i]);
 }
 return digitsArray;
}


public static int DigitsToNumber(List<Integer> digitsArray,int start,int end)
{
 int mulFactor = 10;
 int num = 1;
 int result = 0;
 while (start <= end)
 {
  result += num * digitsArray.get(end--);
  num *= mulFactor;
 }
 return result;
}

Time complexity - O(n), where n is the length of the number in terms of digits.

Reference

• http://www.geeksforgeeks.org/given-a-number-find-next-smallest-palindrome-larger-than-this-number/
• http://stackoverflow.com/questions/7934519/a-better-algorithm-to-find-the-next-palindrome-of-a-number-string