Find the Closest Palindrome

Difficulty: Hard

Asked in: Amazon, Microsoft

Understanding the Problem

Given an integer k, write a program to find the closest integer (not including itself), which is a palindrome.

Problem Note:

An integer is said to be a palindrome if it remains the same when its digits are reserved.
'Closest' means that the absolute difference between two integers should be minimum.
num is a positive integer represented by a string, whose length will not exceed 15 digits.
If two palindromic integers are closest to num and there is a tie between them, then return the smaller one as output.

Example 1

Input: "99"
Output: "101"
Explanation: "88" and "101" are two nearest integers which are palindrome. But "101" is the answer because the absolute difference is minimum between "99" and "101".

Solutions

We will be discussing two approaches for the above problem.

1. Naive approach

As we can see that the closest palindrome to a number can be either less than the number or greater than it. For the greater palindrome, the lower limit is number + 1 while for the lower palindrome, the upper limit is number - 1. So, we move further from the number by one and check if it is palindrome or not. This way we get two palindrome numbers - one lower than the number and one greater than the number. Check which one of them is closest (minimum absolute difference) and return it as an answer.

Pseudo Code

int closestPalindrome(int n)
{
    low = n-1
    
    // will decrease the low till low is a palindrome
    while(!checkPalindrome(low))
        low -= 1
    
    high = n + 1
    
    // will increase the high till high is a palindrome
    while(!checkPalindrome(high))
        high += 1
    
    // checking difference between both
    if ( n - low < high - n)
        return low
    else
        return high
}

Complexity

Time Complexity: O(√N)

Space Complexity: O(1)

2. Efficient Approach

The property of palindrome is the left side of the palindrome is the mirror image of the right side. So, there is a thinking that if we make any of the sides the same as the other, we can achieve our goal.

For example, In the case of “12345”, we mirror “12” to right making it “12321”. Similarly, for 123456, we copy “123” to the right.

Now, the question comes in our mind that which side should we change to make it a palindrome. ( Think!)

We can copy the left part of the number to the right to get the closest palindrome. ( Why?)

Let’s dive deeper into why we copy the left to right and not the vice-versa. Suppose the number is "abcxy".

First way: Copy the second half to the first half, the new palindrome obtained will be "yxcxy" which has an absolute difference of |10000(a−y)+1000(b−x)| from the original number.

Second way: If we copy the first half to the second half of the string, we get "abcba", which has an absolute difference of |10(x−b)+(y−a)|. Trying to change c additionally, in either case, would incur an additional value of at least 100 in the absolute difference.

Thus, we see that it is always better to copy the left to right in such conditions.

There can be cases where you need to check multiple candidate palindromes by changing the middle digits. For Example

1805170811

The first half is 18051. After changing the middle digits, the candidates are 1805005081, 1805115081, and 1805225081. The absolute difference is the minimum for 1805225081. Thus, it is the closest palindrome.

How to get these candidate palindromes? (Think!)

We can keep the middle digit same, increment, and decrement the middle digit by 1 and then mirror the left part to get these candidate palindrome numbers.

So, now we know the process to get the closest palindrome, but let's take a look at some corner cases

If the number is a single-digit number, the closest palindrome is calculated by decrementing 1 from it.
If the number consists of continuous 9 like 99, 999, 9999 ..., then add 2 to it and get the closest palindrome. But in the case of “9”, return 8 as it is single digit and the closest palindrome to it will be 8 and not 11. For example, 99 has the closest palindrome 101
If the number is 10, 100, 1000, and so on, subtract 1 from it to get the closest palindrome.

Pseudo Code

int closestPalindrome(int n)
{
    if(n < 10)
        return n-1
    if(check9(n))
        return n + 2
    
    s = str(n) // string representation of n
        
    // Take First Half of string
    
    firstHalf = s.substr(0, s.length() /2)
    
    // if string is of odd length we are storing the odd digit
    if (s.size() %2)
        odd = s[s.size()/2]
        
    // take second half as reverse of first half
    secondHalf = reverse(firstHalf)
    
    // store the palindrome candidates
    
    pal1 = "" // for same middle digit
    pal2 = "" // for middle -1 digit 
    pal3 = "" // for middle + 1 digit
    
    if(s.size()%2)
    {
        // odd length case
        pal1 = firstHalf + odd + secondHalf
        
        if(odd == '0')
        {
            temp = addCarry(firstHalf, -1)
            pal2 = temp + "9" + reverse(temp)
        } else
            pal2 = firstHalf + str(int(odd) -1) + secondHalf
        
        if(odd == '9')
        {
            temp = addCarry(firstHalf, 1)
            pal3 = temp + '0' + reverse(temp)
        } else
            pal3 = firstHalf + str(int(odd) + 1) + secondHalf
    } 
    else
    {
        // even length case
        pal1 = firstHalf + secondHalf
        
        smallSize = firstHalf.size() // size of first half
        if(firstHalf[smallSize -1] == '0')
            temp = addCarry(firstHalf,-1)
        else
            temp = firstHalf.substr(0,smallSize-1) +
                str(int(firstHalf[smallSize-1]) - 1)
        pal2 = temp + reverse(temp)
        
        if(firstHalf[smallSize-1] == '9')
            temp = addCarry(firstHalf, 1)
        else
            temp = firstHalf.substr(0, smallSize-1) +
                str(int(firstHalf[smallSize-1] - 1))
        
        pal3 = temp + reverse(temp)
    }
    
    // return the closest
    diff1 = abs(n- pal1)
    diff2 = abs(n - pal2)
    diff3 = abs(n - pal3)
    
    if(int(pal1) == n)
        return diff2 <= diff3 ? int(pal2) : int(pal3)
    else if(n > int(pal1))
        return diff1 <= diff3 ? int(pal1 : int(pal3)
    else
        return diff2 <= diff1 ? int(pal2) : int(pal1)
}
// Adding carry to num
string addCarry(string num, int carry)
{
    if(carry == -1)
    {
        itr = num.size() -1
        while( itr >= 0 && num[i] == '0')
            num[itr--] = '9'
        
        if( itr >= 0)
            num[itr] = str(int(num[itr])-1)
    } 
    else
    {
       for(i = num.size() -1 to 0)
       {
           temp = int(num[i])
           num[i] = str((temp + carry)%10)
           carry = (temp + carry) / 10
       }
    }
    
    return num
}

Complexity

Time Complexity: O(No of Digits) (Why?)

Space Complexity: O(No of Digits) (To store the temp variables)