Thursday 24 September 2015

Next larger palindrome

Problem

Given an integer find the immediate larger integer that that which is a palindrome, example 1234212 -> 1234321, 345676 -> 346643.

Solution

Let the integers' digit be abcdef. As number of digits are even we will divide it in two parts, abc and def. Now we reverse first part and it becomes cba. if cba is greater than def then abccba is the answer. If it is smaller we increment the first part and it becomes (abc+1)=suppose xyz, so the answer would be xyzzyx.
Now let's check what happens when number of digits are odd. Let the integer be abcdefg. We divide it into 3 parts. abc, d, efg. if cba is greater than efg then the answer is abcdcba. If it is smaller then abcd is incremented by 1. Suppose (abcd+1)=wxyz. Then the answer is wxyzyxw.

Code

public class NextPalindrome
{
 public static void main(String[] args)
 {
  System.out.println(nextPalindrome(112100));
 }
 public static int nextPalindrome(int num)
 {
  return nextPalindrome(num,true);
 }
 private static int nextPalindrome(
    int num,boolean firstTime)
 {
  String numString=""+num;
  int leftEndIndex=-1;
  int rightStartIndex=-1;
  boolean isOdd=numString.length()%2==1;
  if(isOdd)
  {
   leftEndIndex=numString.length()/2;
   rightStartIndex=leftEndIndex+1;
  }
  else
  {
   leftEndIndex=rightStartIndex=numString.length()/2;
   
  }
  String leftHalf=numString.substring(0,leftEndIndex);
  String rightHalf=numString.substring(rightStartIndex);
  
  String leftReversed=new StringBuffer(leftHalf).
    reverse().toString();
  String palindrome=null;
  if(Integer.parseInt(leftReversed)>Integer.parseInt
    (rightHalf)||!firstTime)
  {
   if(isOdd)
    palindrome=leftHalf+numString.charAt(leftEndIndex)+
    leftReversed;
   else
    palindrome=leftHalf+leftReversed;
   return Integer.parseInt(palindrome);
  }
  else
  {
   if(isOdd)
   {
    String leftAndMiddle=leftHalf+numString.charAt(
    leftEndIndex);
    int incrementedLeft=Integer.parseInt(leftAndMiddle)+1;
    return nextPalindrome(Integer.parseInt(incrementedLeft+
    rightHalf),false);
   }
   else
   {
    int incrementedLeft=Integer.parseInt(leftHalf)+1;
    return nextPalindrome(Integer.parseInt(incrementedLeft+
    rightHalf),false);
   }
  }
  
 }
}

No comments:

Post a Comment