Finding Next Palindrome Number using Java
One approach would be to keep on incrementing the number and after each increment check if the number is a palindrome. But suppose the number is 99990000 then the next palindrome will be 99999999, so 9999 iterations will have to be made. However this approach is crude and having more complexity.
More nuanced approach for finding Palindrome- In this approach that we will follow there are two cases-
- The length of the number is odd
- The length of the number is even
The length of the number is odd
In this case we have the following three scenarios-- Suppose the number is PQRST. We find the middle number i.e. R. Then discard the numbers after R and replace them with the numbers before R in reverse order. For example if number is 45312, then the middle number is 3. Discard the numbers after 3 and replace then with numbers before 3 in reverse order. So the number will be 45354, which is a palindrome and number is greater than the original number 45312.
- Now suppose the number is 12345. After following the above steps we get the number 12321 which is a palindrome but this number is smaller than 12345. In such a scenario we increment the middle value by 1. So the new palindrome will be 12421 which is greater than 12345.
- Now consider the number 12945. After following steps in first point above we get the number as 12921. This number is smaller than original number 12945. In this scenario we cant increment only the middle number since it is 9. We should increment the entire number till the middle number by 1. So increment the number 129 by 1 we get 13045 as the number. Now we find the palindrome for this number using step 1 . So we get the palindrome as 13031 which is greater than original palindrome 12945.
The length of the number is even
In this case we have the following three scenarios-- Suppose the number is PQRS. We find the middle numbers i.e. QR. Then discard the numbers after Q and replace them with the numbers before Q in reverse order including repeating Q again. So the palindrome will be PQQP For example if number is 4531, then the middle number is 53. Discard the numbers after 5 and replace then with numbers before 5 in reverse order including 5 again. So the number will be 4554 , which is a palindrome and number is greater than the original number 4531.
- Now suppose the number is 1459. After following the above steps we get the number 1441 which is a palindrome but this number is smaller than 1459. In such a scenario we increment the middle elements value by 1 each. So the new palindrome will be 1551 which is greater than 1459.
- Now consider the number 1997. After following steps in first point above we get the number as 1991. This number is smaller than original number 1997. In this scenario we cant increment only the middle elements since it is 99. We should increment the entire number till the middle elements by 1. So increment the number 199 by 1 we get 2001 as the number. Now we find the palindrome for this number using step 1 . So we get the palindrome as 2002 which is greater than original palindrome 1997.
package com.javainuse;
public class TestNextPalindrome {
public static void main(String[] args) {
int number1 = 45312;
int number2 = 12345;
int number3 = 12945;
int number4 = 4531;
int number5 = 1459;
int number6 = 1997;
System.out.print("For the number " + number1);
getNextPalindrome(number1);
System.out.print("For the number " + number2);
getNextPalindrome(number2);
System.out.print("For the number " + number3);
getNextPalindrome(number3);
System.out.print("For the number " + number4);
getNextPalindrome(number4);
System.out.print("For the number " + number5);
getNextPalindrome(number5);
System.out.print("For the number " + number6);
getNextPalindrome(number6);
}
private static void getNextPalindrome(int number) {
if (isSizeEven(number)) {
getNextPalindromeForEvenLengthNumbers(number);
}
else {
getNextPalindromeForOddLengthNumbers(number);
}
}
private static boolean isSizeEven(int number) {
if (String.valueOf(number).length() % 2 == 0)
return true;
return false;
}
private static void getNextPalindromeForEvenLengthNumbers(int number) {
StringBuilder testPalindromeString = new StringBuilder();
testPalindromeString.append(number);
StringBuilder convertTopalindrome = new StringBuilder();
convertTopalindrome.append(testPalindromeString.substring(0, testPalindromeString.length() / 2));
convertTopalindrome.append(testPalindromeString.delete(testPalindromeString.length() / 2,
testPalindromeString.length()).reverse());
//if the palindrome is greater than the original number
if (Integer.parseInt(convertTopalindrome.toString()) > number) {
System.out.println(" the next palindrome is " + convertTopalindrome);
}
else {
//get the middle elements in case of even numbers
String middleElements =
convertTopalindrome.substring(convertTopalindrome.length() / 2 - 1,
convertTopalindrome.length() / 2 + 1);
int middleElementsInt = Integer.valueOf(middleElements);
//we are going to increment the middle elements by 1 so check if after this the value is not greater than 99
if (middleElementsInt + 11 < 99) {
convertTopalindrome.replace(convertTopalindrome.length() / 2 - 1,
convertTopalindrome.length() / 2 + 1, String.valueOf(middleElementsInt + 11));
System.out.println(" the next palindrome is " + convertTopalindrome);
}
else {
String numberTillMiddleElement =
convertTopalindrome.substring(0, convertTopalindrome.length() / 2 + 1);
int numberTillMiddleElementInt = Integer.valueOf(numberTillMiddleElement);
convertTopalindrome.replace(0, convertTopalindrome.length() / 2 + 1,
String.valueOf(numberTillMiddleElementInt + 1));
getNextPalindrome(Integer.valueOf(convertTopalindrome.toString()));
}
}
}
private static void getNextPalindromeForOddLengthNumbers(int number) {
StringBuilder testPalindromeString = new StringBuilder();
testPalindromeString.append(number);
StringBuilder convertTopalindrome = new StringBuilder();
convertTopalindrome.append(testPalindromeString.substring(0, testPalindromeString.length() / 2 + 1));
convertTopalindrome.append(testPalindromeString.delete(testPalindromeString.length() / 2,
testPalindromeString.length()).reverse());
//if the palindrome is greater than the original number
if (Integer.parseInt(convertTopalindrome.toString()) > number) {
System.out.println(" the next palindrome is " + convertTopalindrome);
}
else {
char middleElement = convertTopalindrome.charAt(convertTopalindrome.length() / 2);
int middleElementInt = Character.getNumericValue(middleElement);
//we are going to increment the middle element by 1 so check if after this the value is not greater than 9
if (middleElementInt < 9) {
convertTopalindrome.replace(convertTopalindrome.length() / 2,
convertTopalindrome.length() / 2 + 1, String.valueOf(middleElementInt + 1));
System.out.println(" the next palindrome is " + convertTopalindrome);
}
else {
String numberTillMiddleElement =
convertTopalindrome.substring(0, convertTopalindrome.length() / 2 + 1);
int numberTillMiddleElementInt = Integer.valueOf(numberTillMiddleElement);
convertTopalindrome.replace(0, convertTopalindrome.length() / 2 + 1,
String.valueOf(numberTillMiddleElementInt + 1));
getNextPalindrome(Integer.valueOf(convertTopalindrome.toString()));
}
}
}
}
The complexity of this approach will be O(logN).
Download Source Code
Download it - Next Palindrome Implementation using JavaSee Also
Overriding equals() in Java Internal working of ConcurrentHashMap in Java Image Comparison in Java Java - PermGen space vs Heap space Java - PermGen space vs MetaSpace Java 8 Features Java Miscelleneous Topics Java Basic Topics Java- Main Menu Top Java Data Structures and Algorithm Interview Questions