Closest Palindrome Number (absolute difference Is min)
Given a number N. our task is to find the closest Palindrome number whose absolute difference with given number is minimum and absolute difference must be greater than 0.
Examples:
Input : N = 121
Output : 131 or 111
Explanation: Both having equal absolute difference
with the given number.
Input : N = 1234
Output : 1221
Asked In : Amazon
Below is the implementation of above idea :
C++
// C++ Program to find the closest Palindrome // number #include <bits/stdc++.h> using namespace std; // function check Palindrome bool isPalindrome(string n) { for ( int i = 0; i < n.size() / 2; i++) if (n[i] != n[n.size() - 1 - i]) return false ; return true ; } // convert number into String string convertNumIntoString( int num) { // base case: if (num == 0) return "0" ; string Snum = "" ; while (num > 0) { Snum += (num % 10 - '0' ); num /= 10; } return Snum; } // function return closest Palindrome number int closestPalindrome( int num) { // case1 : largest palindrome number // which is smaller to given number int RPNum = num - 1; while (!isPalindrome(convertNumIntoString( abs (RPNum)))) RPNum--; // Case 2 : smallest palindrome number // which is greater than given number int SPNum = num + 1; while (!isPalindrome(convertNumIntoString(SPNum))) SPNum++; // check absolute difference if ( abs (num - RPNum) > abs (num - SPNum)) return SPNum; else return RPNum; } // Driver program to test above function int main() { int num = 121; cout << closestPalindrome(num) << endl; return 0; } |
Java
// Java program to find the closest // Palindrome number import java.io.*; class GFG { // Function to check Palindrome public static boolean isPalindrome(String s) { int left = 0 ; int right = s.length() - 1 ; while (left < right) { if (s.charAt(left) != s.charAt(right)) { return false ; } left++; right--; } return true ; } // Function return closest Palindrome number public static void closestPalindrome( int num) { // Case1 : largest palindrome number // which is smaller to given number int RPNum = num - 1 ; while (isPalindrome(Integer.toString(RPNum)) == false ) { RPNum--; } // Case 2 : smallest palindrome number // which is greater than given number int SPNum = num + 1 ; while (isPalindrome(Integer.toString(SPNum)) == false ) { SPNum++; } // Check absolute difference if (Math.abs(num - SPNum) < Math.abs(num - RPNum)) { System.out.println(SPNum); } else System.out.println(RPNum); } // Driver code public static void main(String[] args) { int n = 121 ; closestPalindrome(n); } } // This code is contributed by kes333hav |
Python3
# Python3 program to find the # closest Palindrome number # Function to check Palindrome def isPalindrome(n): for i in range ( len (n) / / 2 ): if (n[i] ! = n[ - 1 - i]): return False return True # Convert number into String def convertNumIntoString(num): Snum = str (num) return Snum # Function return closest Palindrome number def closestPalindrome(num): # Case1 : largest palindrome number # which is smaller than given number RPNum = num - 1 while ( not isPalindrome( convertNumIntoString( abs (RPNum)))): RPNum - = 1 # Case2 : smallest palindrome number # which is greater than given number SPNum = num + 1 while ( not isPalindrome( convertNumIntoString(SPNum))): SPNum + = 1 # Check absolute difference if ( abs (num - RPNum) > abs (num - SPNum)): return SPNum else : return RPNum # Driver Code if __name__ = = '__main__' : num = 121 print (closestPalindrome(num)) # This code is contributed by himanshu77 |
C#
// C# program to find the closest // Palindrome number using System; class GFG { // Function to check Palindrome public static bool isPalindrome( string s) { int left = 0; int right = s.Length - 1; while (left < right) { if (s[left] != s[right]) { return false ; } left++; right--; } return true ; } // Function return closest Palindrome number public static void closestPalindrome( int num) { // Case1 : largest palindrome number // which is smaller to given number int RPNum = num - 1; while (isPalindrome(RPNum.ToString()) == false ) { RPNum--; } // Case 2 : smallest palindrome number // which is greater than given number int SPNum = num + 1; while (isPalindrome(SPNum.ToString()) == false ) { SPNum++; } // Check absolute difference if (Math.Abs(num - SPNum) < Math.Abs(num - RPNum)) { Console.WriteLine(SPNum); } else Console.WriteLine(RPNum); } // Driver code public static void Main( string [] args) { int n = 121; closestPalindrome(n); } } // This code is contributed by ukasp |
Javascript
// JavaScript Program to find the closest Palindrome // number // function check Palindrome function isPalindrome(n) { for (let i = 0; i < Math.floor(n.length / 2); i++) if (n[i] != n[n.length - 1 - i]) return false ; return true ; } // convert number into String function convertNumIntoString(num) { // base case: if (num == 0) return "0" ; let Snum = num + '' ; return Snum; } // function return closest Palindrome number function closestPalindrome(num) { // case1 : largest palindrome number // which is smaller to given number let RPNum = num - 1; while (!isPalindrome(convertNumIntoString(Math.abs(RPNum)))) RPNum--; // Case 2 : smallest palindrome number // which is greater than given number let SPNum = num + 1; while (!isPalindrome(convertNumIntoString(SPNum))) SPNum++; // check absolute difference if (Math.abs(num - RPNum) > Math.abs(num - SPNum)) return SPNum; else return RPNum; } // Driver program to test above function let num = 121; console.log(closestPalindrome(num), "</br>" ); // This code is contributed by prophet1999 |
PHP
<?php // PHP Program to find the // closest Palindrome number // function check Palindrome function isPalindrome( $n ) { for ( $i = 0; $i < floor ( strlen ( $n ) / 2); $i ++) if ( $n [ $i ] != $n [ strlen ( $n ) - 1 - $i ]) return false; return true; } // convert number into String function convertNumIntoString( $num ) { // base case: if ( $num == 0) return "0" ; $Snum = "" ; while ( $num > 0) { $Snum .= ( $num % 10 - '0' ); $num =(int)( $num / 10); } return $Snum ; } // function return closest // Palindrome number function closestPalindrome( $num ) { // case1 : largest palindrome number // which is smaller to given number $RPNum = $num - 1; while (!isPalindrome(convertNumIntoString( abs ( $RPNum )))) $RPNum --; // Case 2 : smallest palindrome number // which is greater than given number $SPNum = $num + 1; while (!isPalindrome(convertNumIntoString( $SPNum ))) $SPNum ++; // check absolute difference if ( abs ( $num - $RPNum ) > abs ( $num - $SPNum )) return $SPNum ; else return $RPNum ; } // Driver code $num = 121; echo closestPalindrome( $num ). "\n" ; // This code is contributed by mits ?> |
111
Complexity Analysis:
- The time complexity of the given algorithm is O(num*log(num)) since it loops through each digit of the input number.
- The auxiliary space of the algorithm is O(1) since it does not use any additional space that depends on the input size.
Efficient Approach: This approach is based on a little bit of mathematical understanding and logical intuition.
For any possible number, there are 5 cases:
(Say the number is 4723)
Case 1 – The next closest palindrome has one digit extra : So here it will be 10001.
Case 2 – The next closest palindrome has one digit less: So here it will be 999.
Case 3 – The next closest palindrome has the same number of digits.
For case 3 there are 3 subcases:
The middle digit remains same. Postfix is the mirror image of prefix. So here 47(prefix) – 74(postfix)–>4774.
The middle digit increases by 1. Postfix is the mirror image of prefix. So here 4884.
The middle digit decreases by 1. Postfix is the mirror image of prefix. So here 4664.
Among these 5 candidates:
The candidate having the least absolute difference from the original number is the answer. In this case it is 4774.
Overall, the program iterates over the candidate palindromic numbers and finds the one that is closest to the input number. The program uses basic mathematical operations such as finding the prefix of the input number and creating palindromic versions of numbers to achieve this.
Follow below steps to solve this problem:
- Create a vector to store candidate palindromic numbers.
- Determine the length of the input number and the middle index.
- If the input number has a length of 1, return the string of that number minus 1 as the closest palindromic number.
- Add two candidate palindromic numbers to the vector: the smallest palindromic number greater than the input number, and the largest palindromic number smaller than the input number.
- Create a vector of three numbers that have the same prefix as the input number: the prefix itself, the prefix incremented by 1, and the prefix decremented by 1.
- For each number in the prefix vector, create a palindromic number by appending its reverse to itself. If the input number has an odd length, remove the last character of the reverse before appending.
- Add each candidate palindromic number to the vector.
- Iterate over the candidate vector and find the candidate with the smallest absolute difference to the input number. If there are multiple candidates with the same absolute difference, select the smallest one.
C++14
// C++ Program to find the closest Palindromic number #include <bits/stdc++.h> using namespace std; string closestPalindrome(string n) { vector< long > candidates; int len = n.length(); int mid = (len + 1) / 2; if (len == 1) return to_string(stoi(n) - 1); candidates.push_back( pow (10, len) + 1); candidates.push_back( pow (10, len - 1) - 1); long prefix = stol(n.substr(0, mid)); vector< long > temp = { prefix, prefix + 1, prefix - 1 }; for ( long i : temp) { string res = to_string(i); if (len & 1) res.pop_back(); reverse(res.begin(), res.end()); string peep = to_string(i) + res; candidates.push_back(stol(peep)); } long minDiff = LONG_MAX, result, tip = stol(n); for ( int i = 0; i < 5; i++) { if (candidates[i] != tip && minDiff > abs (candidates[i] - tip)) { result = candidates[i]; minDiff = abs (candidates[i] - tip); } else if ( abs (candidates[i] - tip) == minDiff) result = min(result, candidates[i]); } return to_string(result); } // driver's code int main() { string num = "489" ; cout << closestPalindrome(num) << endl; return 0; } |
Java
import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class ClosestPalindrome { public static String closestPalindrome(String n) { // Initialize a list to store the candidate palindromic numbers List<Long> candidates = new ArrayList<>(); // Get the length of the input number n int length = n.length(); // Calculate the index of the middle element (or the element just after the middle for even-length numbers) int mid = (length + 1 ) / 2 ; // If the input number has only one digit, the closest palindromic number is (n-1) if (length == 1 ) { long num = Long.parseLong(n); return String.valueOf(num - 1 ); } // Add two candidates: (10^n + 1) and (10^(n-1) - 1) candidates.add(( long ) Math.pow( 10 , length) + 1 ); candidates.add(( long ) Math.pow( 10 , length - 1 ) - 1 ); // Extract the prefix (first half) of the input number int prefix = Integer.parseInt(n.substring( 0 , mid)); // Generate three possible prefixes by incrementing and decrementing the original prefix List<Integer> temp = Arrays.asList(prefix, prefix + 1 , prefix - 1 ); // Construct the candidate palindromic numbers using the generated prefixes for ( int i : temp) { String res = String.valueOf(i); // If the length of the input number is odd, exclude the last character while constructing the palindromic number if ((length & 1 ) != 0 ) { res = res.substring( 0 , res.length() - 1 ); } // Create the palindromic number by appending the reverse of the prefix String peep = i + new StringBuilder(res).reverse().toString(); candidates.add(Long.parseLong(peep)); } // Initialize variables to keep track of the minimum difference and the closest palindromic number long minDiff = Long.MAX_VALUE; long result = Long.parseLong(n); long tip = Long.parseLong(n); // Iterate through the candidate palindromic numbers and find the closest one to the input number for ( int i = 0 ; i < 5 ; i++) { long candidate = candidates.get(i); if (candidate != tip && minDiff > Math.abs(candidate - tip)) { result = candidate; minDiff = Math.abs(candidate - tip); } else if (Math.abs(candidate - tip) == minDiff) { result = Math.min(result, candidate); } } return String.valueOf(result); } public static void main(String[] args) { String num = "489" ; System.out.println(closestPalindrome(num)); } } // This code is contributed by shivamgupta0987654321 |
Python3
def closestPalindrome(n): # Initialize a list to store the candidate palindromic numbers candidates = [] # Get the length of the input number n length = len (n) # Calculate the index of the middle element (or the element just after the middle for even-length numbers) mid = (length + 1 ) / / 2 # If the input number has only one digit, the closest palindromic number is (n-1) if length = = 1 : return str ( int (n) - 1 ) # Add two candidates: (10^n + 1) and (10^(n-1) - 1) candidates.append( 10 * * length + 1 ) candidates.append( 10 * * (length - 1 ) - 1 ) # Extract the prefix (first half) of the input number prefix = int (n[:mid]) # Generate three possible prefixes by incrementing and decrementing the original prefix temp = [prefix, prefix + 1 , prefix - 1 ] # Construct the candidate palindromic numbers using the generated prefixes for i in temp: res = str (i) # If the length of the input number is odd, exclude the last character while constructing the palindromic number if length & 1 : res = res[: - 1 ] # Create the palindromic number by appending the reverse of the prefix peep = str (i) + res[:: - 1 ] candidates.append( int (peep)) # Initialize variables to keep track of the minimum difference and the closest palindromic number minDiff = float ( 'inf' ) result = tip = int (n) # Iterate through the candidate palindromic numbers and find the closest one to the input number for i in range ( 5 ): if candidates[i] ! = tip and minDiff > abs (candidates[i] - tip): result = candidates[i] minDiff = abs (candidates[i] - tip) # If there are multiple candidates with the same difference, choose the smaller one elif abs (candidates[i] - tip) = = minDiff: result = min (result, candidates[i]) return str (result) # driver's code num = "489" print (closestPalindrome(num)) |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { // Function to find the closest Palindromic number static string ClosestPalindrome( string n) { List< long > candidates = new List< long >(); int len = n.Length; int mid = (len + 1) / 2; if (len == 1) return ( long .Parse(n) - 1).ToString(); // Adding candidates with all 9s and all 0s candidates.Add(( long )Math.Pow(10, len) + 1); candidates.Add(( long )Math.Pow(10, len - 1) - 1); long prefix = long .Parse(n.Substring(0, mid)); List< long > temp = new List< long >{ prefix, prefix + 1, prefix - 1 }; // Generating candidates by combining prefix and its // variations foreach ( long i in temp) { string res = i.ToString(); if ((len & 1) == 1) res = res.Remove(res.Length - 1); res = new string (res.Reverse().ToArray()); string peep = i.ToString() + res; candidates.Add( long .Parse(peep)); } long minDiff = long .MaxValue, result = 0, tip = long .Parse(n); // Finding the closest palindrome among candidates for ( int i = 0; i < 5; i++) { if (candidates[i] != tip && minDiff > Math.Abs(candidates[i] - tip)) { result = candidates[i]; minDiff = Math.Abs(candidates[i] - tip); } else if (Math.Abs(candidates[i] - tip) == minDiff) { result = Math.Min(result, candidates[i]); } } return result.ToString(); } // Main method to test the ClosestPalindrome function static void Main() { string num = "489" ; Console.WriteLine(ClosestPalindrome(num)); } } |
Javascript
function closestPalindrome(n) { // Initialize an array to store the candidate palindromic numbers let candidates = []; // Get the length of the input number n let len = n.length; // Calculate the index of the middle element (or the element just // after the middle for even-length numbers) let mid = Math.floor((len + 1) / 2); // If the input number has only one digit, the closest palindromic number is (n-1) if (len === 1) return (parseInt(n) - 1).toString(); // Add two candidates: (10^n + 1) and (10^(n-1) - 1) candidates.push(Math.pow(10, len) + 1); candidates.push(Math.pow(10, len - 1) - 1); // Extract the prefix (first half) of the input number let prefix = parseInt(n.substring(0, mid)); // Generate three possible prefixes by incrementing and decrementing the original prefix let temp = [prefix, prefix + 1, prefix - 1]; // Construct the candidate palindromic numbers using the generated prefixes for (let i of temp) { let res = i.toString(); if (len % 2 === 1) res = res.slice(0, -1); res = res.split( "" ).reverse().join( "" ); let peep = i.toString() + res; candidates.push(parseInt(peep)); } // Initialize variables to keep track of the // minimum difference and the closest palindromic number let minDiff = Number.MAX_SAFE_INTEGER; let result, tip = parseInt(n); // Iterate through the candidate palindromic numbers // and find the closest one to the input number for (let i = 0; i < 5; i++) { if (candidates[i] !== tip && minDiff > Math.abs(candidates[i] - tip)) { result = candidates[i]; minDiff = Math.abs(candidates[i] - tip); } else if (Math.abs(candidates[i] - tip) === minDiff) result = Math.min(result, candidates[i]); } return result.toString(); } // Driver's code let num = "489" ; console.log(closestPalindrome(num)); |
484
Time complexity: O(len(num))
Auxiliary space: O(1)