Home » Technical Interview Questions » String Interview Questions » Find the Closest Palindrome number

Find the Closest Palindrome number


Reading Time - 3 mins

Problem

In Find the Closest Palindrome number problem we have given a number n. Find a number which is a palindrome and the absolute difference between the palindromic number and n is as minimum as possible except zero. If there is more than one number satisfying this condition then print the smaller number.

Find the Closest Palindrome number

Example

Input

123

Output

121

Explanation

A palindromic number smaller than 123 is 121 and their absolute difference is 2. Similarly, a  palindromic number greater than 123 is 131 and their absolute difference is 8. So the palindromic number with minimum absolute difference 121.

Brute force approach

As in case if there is more than one number satisfying the minimum absolute difference palindromic condition then we have to select the smaller number. So we first start with decreasing the number and check if it is a palindrome or not. Then we alternatively increase and decrease the given number until we find a palindromic number.

Implementation For Find the Closest Palindrome number

C++ code

// 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 closestPlandrome(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 << closestPlandrome(num) << endl; 
return 0; 
}
111

Java code

public class Solution {
    public String nearestPalindromic(String n) {
        long num = Long.parseLong(n);
        for (long i = 1;; i++) {
            if (isPalindrome(num - i))
                return "" + (num - i);
            if (isPalindrome(num + i))
                return "" + (num + i);
        }
    }
    boolean isPalindrome(long x) {
        long t = x, rev = 0;
        while (t > 0) {
            rev = 10 * rev + t % 10;
            t /= 10;
        }
        return rev == x;
    }
}
121
111

Time complexity

O(√n)  because in the worst case we may need to traverse 2*√n numbers.

READ  Fizz Buzz Leetcode

Space complexity

O(1)  because we are using constant space.

Efficient Approach

This is the optimized approach. Here we will generate three numbers.

First number

We divide the string into parts and takes a mirror of the left part of the string to the right part to make it a palindromic string.

Second number

We divide the string into parts then add one in the left part of the string and takes a mirror of the left part of the string to the right part to make it a palindromic string.

Third number

We divide the string into parts then subtract one from the left part of the string and takes a mirror of the left part of the string to the right part to make it a palindromic string.

Now we will compare these three numbers and minimum. The number with the minimum absolute difference with the given number is our answer and in case of tie minimum of them is our answer.

Implementation For Find the Closest Palindrome number

C++ code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
    ll mirror(ll ans) {
    string a = to_string(ans);
    int i = 0;
    int j = a.length()-1;
    while (i < j) {
        a[j--] = a[i++];
    }
    return stoll(a,nullptr,10);
} 
 string nearestPalindromic(string n) {
    int order =pow(10, n.length()/2);
    ll ans = stoll(n,nullptr,10);
    ll noChange = mirror(ans);
    ll larger = mirror((ans/order)*order + order+1);
    ll smaller = mirror((ans/order)*order - 1 );
    if ( noChange > ans) {
        larger =  min(noChange, larger);
    } else if ( noChange < ans) {
        smaller = max(noChange, smaller); 
    }       
    return to_string( ans - smaller <= larger - ans ? smaller :larger) ;
    }
int main()
{   
 string s="129";
 s=nearestPalindromic(s);
 cout<<s<<endl;
return 0;
}
131

Java code

public String nearestPalindromic(String n) {
    int order = (int) Math.pow(10, n.length()/2);
    Long ans = Long.valueOf(new String(n));
    Long noChange = mirror(ans);
    Long larger = mirror((ans/order)*order + order+1);
    Long smaller = mirror((ans/order)*order - 1 );
    if ( noChange > ans) {
        larger = (long) Math.min(noChange, larger);
    } else if ( noChange < ans) {
        smaller = (long) Math.max(noChange, smaller); 
    }       
    return String.valueOf( ans - smaller <= larger - ans ? smaller :larger) ;
}
Long mirror(Long ans) {
    char[] a = String.valueOf(ans).toCharArray();
    int i = 0;
    int j = a.length-1;
    while (i < j) {
        a[j--] = a[i++];
    }
    return Long.valueOf(new String(a));
}
129
131

Time complexity

O(len) where len is the length of the string.

READ  Valid Parenthesis String

Space complexity

O(1)  because we are using constant space.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions