For a given a number, find the next smallest palindrome larger than this number.
Examples:
1. If the input number is “3 4 6 5 6”, the output should be “3 4 7 4 3”.
2. If the input number is “9 9 9 9”, the output should be “1 0 0 0 1”.
Approach:
There can be three different cases those should be handled separately.
1) The input number is palindrome and has all 9s.
Example
Input: 9 9 9 9
Output:1 0 0 0 1.
It can be get by adding 2 into the number.
2) The input number is not palindrome.
Example
Input: 2 3 4 5
Output:2 4 4 2.
3) The input number is palindrome and doesn’t have all 9s.
Example
Input: 2 3 3 2.
Output:2 4 4 2.
package com.geeks;
public class NextGreaterPalindrome {
/**
* getNextPalindrome
* @param number
* @author rajesh.dixit
* @return
*/
private static void getNextPalindrome(intnumber) {
/** To handle the case when all digits in number are 9. */
if((int)Math.log10(number+1)!=(int)Math.log10(number)) {
System.out.println("All 9s");
System.out.println("Next Palidrome for the number "+ number +" is: "+(number+2));
}
int[] array = getNumberArray(number);
int length = array.length;
// find the index of middle digit
int mid = length/2;
// A boolean variable to check if copy of left side to right is sufficient or not
boolean leftSmaller = false;
// end of left side is always 'mid -1'
int i = mid - 1;
// Beginning of right side depends if n is odd or even
int j = (length%2)!=0? mid + 1 : mid;
while(i >= 0 && array[i]==array[j]) {
i--;j++;
}
/*
* leftSmaller when the left side array small then right one
* or left array is equal to right array (i<0)
* */
if(i<0 || array[i]<array[j]) {
leftSmaller = true;
}
// Copy the mirror of left to right
if(!leftSmaller) {
while (i >= 0) {
array[j] = array[i];
j++;
i--;
}
} else {
/* Case: When left side is small or equal to right side.
* need to increment the middle element.
* */
i = mid - 1;
int carry = 1;
if(length%2==1) {
inttemp = array[mid]+carry;
carry = temp/10;
array[mid] = temp%10;
j = mid+1;
} else {
j = mid;
}
while(i>=0) {
inttemp = array[i]+carry;
carry = temp/10;
temp = temp%10;
array[j] = temp;
array[i] = temp;
i--;j++;
}
}
System.out.print("Next Palidrome for the number "+ number +" is: ");
printArray(array);
}
/**
* Convert number into int Array
* @param number
* @return int[] array
*/
private static int[] getNumberArray(intnumber) {
int length = (int)(Math.log10(number)+1);
int[] array = newint[length];
for (inti = 0; i < length; i++) {
int val = number%10;
number = number/10;
array[length-i-1] = val;
}
return array;
}
/**
* Utility Method to print numbers.
* @param number
*/
private static void printArray(int[] number) {
for(intvalue : number) {
System.out.print(value);
}
}
/**
* Driver Method
* @param args
*/
public static void main(String[] args) {
int number = 34656;
getNextPalindrome(number);
}
}
No comments:
Post a Comment