Next Smallest Palindrome problem in Java
The Next Smallest Palindrome problem involves finding the smallest palindrome larger than a given number. A palindrome is a number that reads the same backward as forward. For example, the next smallest palindrome for 123 is 131, and for 999, it's 1001.
Example 1
Input: 123
Output: 131
Explanation: Mirror the first half "12" to get "121". Since 121 is not greater than 123, increment "12" to "13" and mirror to get "131".
Example 2
Input: 999
Output: 1001
Explanation: All digits are 9, so the next smallest palindrome is 1001, formed by adding 2 to the input.
Approach 1: Using Incremental Check
The incremental approach to finding the next smallest palindrome involves incrementing the given number and checking if the incremented number is a palindrome. The process continues until a palindrome is found.
Algorithm
Step 1: Take an input value.
Step 2: Increment the given number by 1.
Step 3: Check if the incremented number is a palindrome.
Step 4: If it is a palindrome, return the number.
Step 5: If not, repeat steps 2-4.
FileName: NextSmallestPalindromeIncrmental.java
public class NextSmallestPalindromeIncrmental { public static void main(String[] args) { int num = 123; // Example input System.out.println("Next Palindrome: " + findNextPalindrome(num)); } // Function to find the next smallest palindrome greater than the given number public static int findNextPalindrome(int num) { num++; // Increment the number by 1 // Continue incrementing until we find a palindrome while (!isPalindrome(num)) { num++; } return num; // Return the next palindrome } // Function to check if a number is a palindrome public static boolean isPalindrome(int num) { String str = Integer.toString(num); // Convert the number to a string int len = str.length(); // Get the length of the string // Check each character from the start with the corresponding character from the end for (int i = 0; i < len / 2; i++) { if (str.charAt(i) != str.charAt(len - 1 - i)) { return false; // Return false if characters do not match } } return true; // Return true if all characters match } }
Output
Next Palindrome: 131
Time Complexity: The time complexity of an approach is O(N * M), where N is the number of digits and M is the number of increments needed to find the next palindrome.
Space Complexity: The space complexity of an approach is O(N), where N is the number of digits in the number, as we store the number as a string to check for palindrome properties.
Approach 2: Mirroring Technique
The mirroring technique is used to find the next smallest palindrome involves creating a palindrome by mirroring the first half of the given number. If the created palindrome is not greater than the original number, the first half is incremented, and the process is repeated.
Algorithm
Step 1: Convert the number to a string.
Step 2: Split the string into the first half.
Step 3: Mirror the first half to form a palindrome.
Step 4: If the formed palindrome is greater than the original number, return it.
Step 5: If not, increment the first half, mirror it again, and return the new palindrome.
FileName: NextSmallestPalindromeMirror.java
public class NextSmallestPalindromeMirror { public static void main(String[] args) { int num = 123; // Example input System.out.println("Next Palindrome: " + findNextPalindrome(num)); } // Function to find the next smallest palindrome greater than the given number public static int findNextPalindrome(int num) { String str = Integer.toString(num); // Convert the number to a string int len = str.length(); // Get the length of the string // Get the first half of the string (including the middle character if the length is odd) String firstHalf = str.substring(0, (len + 1) / 2); // Create a palindrome by mirroring the first half String palindrome = mirror(firstHalf); // Check if the created palindrome is greater than the original number if (Integer.parseInt(palindrome) > num) { return Integer.parseInt(palindrome); // Return the palindrome if it's greater } // Increment the first half and create a new palindrome firstHalf = increment(firstHalf); palindrome = mirror(firstHalf); return Integer.parseInt(palindrome); // Return the new palindrome } // Function to create a palindrome by mirroring the first half private static String mirror(String firstHalf) { StringBuilder sb = new StringBuilder(firstHalf); // Create a StringBuilder from the first half String secondHalf = sb.reverse().toString(); // Reverse the first half to get the second half // Combine the first half and the mirrored second half to form a palindrome return firstHalf + secondHalf.substring((firstHalf.length() + 1) % 2); } // Function to increment the first half private static String increment(String firstHalf) { int num = Integer.parseInt(firstHalf); // Convert the first half to an integer num++; // Increment the integer return Integer.toString(num); // Convert the incremented integer back to a string } }
Output
Next Palindrome: 131
Time Complexity: The time complexity of an algorithm is O(N), where N is the number of digits in the number. This is because mirroring and incrementing the first half are linear operations with respect to the length of the number.
Space Complexity: The space complexity of an algorithm is O(N), where N is the number of digits in the number. This is due to the storage required for string operations and constructing the palindrome.