Given a number, find the next smallest palindrome larger than the number. For example if the number is 125, next smallest palindrome is 131.
Java program :
Java program :
public class NextPalindrome {
public static void main(String[] args) {
int n = 2133;
// temp variable to perform operations on n
int temp = n;
// calculate the number of digits
int digits = 0;
while (temp != 0) {
temp = temp / 10;
digits++;
}
// edge case if the given number contains all 9 s like 9 or 99 or 999
// or...,round off to next number
int divider = (int) Math.pow(10, digits);
if ((n + 1) % divider == 0) {
n = n + 1;
digits++;
}
if (digits == 0)
return;
// handling the special case of single digit numbers
if (digits == 1) {
System.out.println("Next higher palindrome is : " + n + 1);
return;
}
// create array of size digits to store the digits of the given number
int[] a = new int[digits];
temp = n;
for (int i = digits - 1; i >= 0 && temp != 0; i--) {
a[i] = temp % 10;
temp = temp / 10;
}
// now array contains the digits in same order as of number
int nextPalindrome = 0;
boolean isPalindrome = false;// used for track whether we got palindrome
// or not
while (!isPalindrome) {
// create mirror image of the given number
createMirrorImage(a);
nextPalindrome = constructNumber(a);
if (nextPalindrome <= n) {
int middle = (int) Math.ceil(digits / 2);
// if the middle digit is 9 then round off to the next higher
// number
if (digits % 2 == 0) {
if (a[digits / 2] == 9) {
a[middle] = 0;
a[middle - 1] = 0;
a[middle - 2] += 1;
} else {
a[middle] += 1;
a[middle - 1] += 1;
}
} else {
if (a[middle] == 9) {
a[middle] = 0;
a[middle - 1] = a[middle - 1] + 1;
} else {
a[middle] += 1;
}
}
} else {
isPalindrome = true;
}
}
System.out.println("Next higher palindrome is : " + nextPalindrome);
}
private static int constructNumber(int[] a) {
int num = 0;
for (int i = 0; i < a.length; i++) {
num = num * 10 + a[i];
}
return num;
}
private static void createMirrorImage(int[] a) {
int length = a.length;
for (int i = 0, j = length - 1; i <= j; i++, j--) {
a[j] = a[i];
}
}
}
Refer : http://www.ardendertat.com/2011/12/01/programming-interview-questions-19-find-next-palindrome-number/
No comments:
Post a Comment