13 Apr 2014

Next Palindrome

Problem Statement: 
                     Given a number find the next Palindrome Number

Solution:
    
In the given problem , we take two pointers one at left and the other on right, we start comparing i and n-i.
The difference of left and right digit (which are multiplied by bases) is added to the number , in case the right digit is greater, we match up the effect introduced by the difference which was added in the previous step.

Time Complexity: O(n)
Space Complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
  * Get next pallindrome
  */
 public static int nextPanlindrome(int num) {

  if(isPalindrome(num))
   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 += left - right  ;   //------(1)

   base *=10;

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

        //number of digits are even,
    if(start == end - 1) 
     num += base/10;
   }
   temp = num + "";
  }

  return num;
 }

 /**
  * Checks if a number is pallindriome
  * @param num
  * @return
  */
 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);
 }

In case of any clarification , suggestion or enhancement of code , please comment.
Happy Coding !! :)    

No comments:

Post a Comment