28 Oct 2013

Next Pallindrome

Problem Statement: 
   Given a number , find the next Palindrome.

Solution:

Concept:  

  1. Convert number to String.
  2. Take base as 1, which will be used to get left and right pointers, in subsequent steps, 
  3. Multiple Base by 10 at even iteration of loop till half the length of the string. 
  4. Take right and left pointer pointing to left and right digits in the string.
  5. Add the difference of left and right to the number
  6. if right is greater left the number would become smaller, therefore increment the next digit to the left of right.
  7. If the number is even and left and right pointer points to adjacent digits, increment right pointer

 Please refer to Source Code

 /**
  * Get next pallindrome
  * @param num
  * @return
  */
 public static int nextPanlindrome(int num) {

  if(isPalindrome(num)) //skip if number entered is pallindrome
   num++;

  String temp = num + "";
  int end=temp.length() -1;
  int base=1;

  for(int start = 0; start < end; start++, end--)
  {

   // Gives the right digit
   int right = Integer.parseInt(temp.charAt(end)+"") * base;

   // Gives the left digit
   int left = Integer.parseInt(temp.charAt(start)+"") * base;

   // add differnce to the number
   num = num + left - right  ;   //------(1)

   base *=10;

   if(right > left)
   {
    num += base;  // for incresing the value of number which got decreased at (1)

    // previous step indroduces asymmetry if its a even number.
    if(start == end - 1)  // For even numbers eg. case 8468 (adjacent digits)
     num += base/10;
   }
   temp = num + "";
  }

  return num;
 }


 public static boolean  isPalindrome(int num) {
  int reverse = 0, temp=num;

  while( temp != 0 ) {
   reverse = reverse * 10;
   reverse = reverse + temp%10;
   temp = temp/10;
  }
  return (num == reverse ? true: false);
 }


This is one of the many ways of getting the next Palindrome number w.r.t a given number.
Any comment or suggestion for any kind of code optimization or any other better approach is most welcome.

Happy Coding !! :)

No comments:

Post a Comment