Solution For Find The Closest Palindrome

Problem:

Given an integer n, find the closest palindrome number to n.

A palindrome number is defined as a number that remains the same when its digits are reversed. For example, 121 is a palindrome number.

If there is a tie, return the smaller palindrome number as the answer.

Example:

Input: n = 1215
Output: 1221
Explanation: The closest palindrome number to 1215 is 1221, which is a palindrome number.

Input: n = 123456
Output: 123321
Explanation: The closest palindrome number to 123456 is 123321, which is a palindrome number.

Approach:

The approach to solve this problem is to find the next palindrome number greater than n and the next palindrome number smaller than n. Then we can compare the absolute difference of these two palindrome numbers with n and return the smaller one.

Given a number n, we can find the next palindrome number greater than n by first converting the number to an array of digits. Then, we start from the middle and move towards the ends of the array. If the digits on both ends are not equal, we can change one of them to make them equal and continue our search. If the digit in the middle is less than 9, we can increase it by 1 and return the array as the next palindrome number. If the digit in the middle is already 9, we have to set it to 0 and continue our search.

Similarly, we can find the next palindrome number smaller than n by following the same approach, starting from the middle and moving towards the ends of the array.

Once we have the next palindrome numbers greater than and smaller than n, we can compare their absolute differences with n and return the smaller palindrome number.

Solution in Python:

“`
class Solution:
def nearestPalindromic(self, n: str) -> str:
# helper function to convert array of digits to integer
def to_int(arr):
num = 0
for d in arr:
num = num * 10 + d
return num

    # helper function to convert integer to array of digits
    def to_arr(num):
        arr = []
        while num > 0:
            arr.append(num % 10)
            num //= 10
        return arr[::-1]

    # helper function to check if a number is palindrome
    def is_palindrome(arr):
        i, j = 0, len(arr) - 1
        while i < j:
            if arr[i] != arr[j]:
                return False
            i += 1
            j -= 1
        return True

    # convert n to an array of digits
    arr = [int(x) for x in n]
    len_arr = len(arr)
    mid = len_arr // 2

    # search for next palindrome number greater than n
    i, j = mid - 1, mid + 1
    while i >= 0 and j < len_arr:
        if arr[i] != arr[j]:
            break
        i -= 1
        j += 1
    if i < 0 or j >= len_arr or arr[i] < arr[j]:
        arr[mid] += 1
        i, j = mid - 1, mid + 1
        while i >= 0 and j < len_arr:
            arr[j] = arr[i]
            i -= 1
            j += 1
    else:
        i, j = mid - 1, mid + 1
        while i >= 0 and j < len_arr:
            arr[j] = arr[i]
            i -= 1
            j += 1

    num1 = to_int(arr)

    # search for next palindrome number smaller than n
    arr = [int(x) for x in n]
    i, j = mid - 1, mid + 1
    while i >= 0 and j < len_arr:
        if arr[i] != arr[j]:
            break
        i -= 1
        j += 1
    if i < 0 or j >= len_arr or arr[i] > arr[j]:
        arr[mid] -= 1
        i, j = mid - 1, mid + 1
        while i >= 0 and j < len_arr:
            arr[j] = arr[i]
            i -= 1
            j += 1
        if arr[0] == 0:
            arr.pop(0)
            len_arr -= 1
            mid = len_arr // 2
            if len_arr < 2 or arr[mid] > 0:
                arr[mid] -= 1
            else:
                arr = [9] * (len_arr - 1)
                arr.insert(0, 1)
    else:
        i, j = mid - 1, mid + 1
        while i >= 0 and j < len_arr:
            arr[j] = arr[i]
            i -= 1
            j += 1

    num2 = to_int(arr)

    # compare the absolute differences and return the smaller palindrome number
    if abs(num1 - int(n)) < abs(num2 - int(n)):
        return str(num1)
    elif abs(num1 - int(n)) > abs(num2 - int(n)):
        return str(num2)
    elif is_palindrome(to_arr(num1 - 1)):
        return str(num1 - 1)
    elif is_palindrome(to_arr(num1 + 1)):
        return str(num1 + 1)
    elif is_palindrome(to_arr(num2 - 1)):
        return str(num2 - 1)
    else:
        return str(num2 + 1)

“`

Time Complexity:

The time complexity of this solution is O(n), where n is the number of digits in the input integer. We need to process the input integer two times to find the next palindrome numbers, and the time complexity of processing each digit is constant. We also need to check if each number we generate is a palindrome, which takes O(n) time. Finally, we need to compare the absolute differences of the two palindrome numbers with the input integer, which takes constant time. Therefore, the overall time complexity is O(n).

Step by Step Implementation For Find The Closest Palindrome

public class Solution {
    public String nearestPalindromic(String n) {
        // if n is a palindrome, then return n
        if (isPalindrome(n)) {
            return n;
        }
        
        // find the closest palindrome that is smaller than n
        String smaller = findSmallerPalindrome(n);
        
        // find the closest palindrome that is larger than n
        String larger = findLargerPalindrome(n);
        
        // compare the two and return the one that is closest to n
        if (Math.abs(Long.parseLong(n) - Long.parseLong(smaller)) < Math.abs(Long.parseLong(larger) - Long.parseLong(n))) {
            return smaller;
        } else {
            return larger;
        }
    }
    
    // helper function to find the next smallest palindrome
    private String findSmallerPalindrome(String n) {
        // if n has an even number of digits, then the next smallest palindrome will have the same number of digits
        if (n.length() % 2 == 0) {
            return findSmallerPalindromeHelper(n, n.length() / 2 - 1, n.length() / 2);
        } else { // if n has an odd number of digits, then the next smallest palindrome will have one less digit
            return findSmallerPalindromeHelper(n, n.length() / 2, n.length() / 2);
        }
    }
    
    // helper function to find the next largest palindrome
    private String findLargerPalindrome(String n) {
        // if n has an even number of digits, then the next largest palindrome will have the same number of digits
        if (n.length() % 2 == 0) {
            return findLargerPalindromeHelper(n, n.length() / 2 - 1, n.length() / 2);
        } else { // if n has an odd number of digits, then the next largest palindrome will have one more digit
            return findLargerPalindromeHelper(n, n.length() / 2, n.length() / 2 + 1);
        }
    }
    
    // helper function to see if a string is a palindrome
    private boolean isPalindrome(String s) {
        for (int i = 0; i < s.length() / 2; i++) {
            if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
                return false;
            }
        }
        return true;
    }
    
    // helper function to find the next smallest palindrome with an even number of digits
    private String findSmallerPalindromeHelper(String n, int left, int right) {
        while (left >= 0 && n.charAt(left) == n.charAt(right)) {
            left--;
            right++;
        }
        
        // if we reached the end without finding a palindrome, then the next smallest palindrome will have one less digit
        if (left < 0) {
            return findSmallerPalindromeHelper(n, n.length() / 2 - 1, n.length() / 2);
        }
        
        // if we found a palindrome, then we need to see if we can make it smaller
        if (n.charAt(left) > n.charAt(right)) {
            // we can make the palindrome smaller by decrementing the left and right pointers
            return findSmallerPalindromeHelper(n, left - 1, right + 1);
        } else { // if we can't make the palindrome smaller, then we need to copy it over
            char[] arr = n.toCharArray();
            while (left >= 0) {
                arr[right] = arr[left];
                left--;
                right++;
            }
            return new String(arr);
        }
    }
    
    // helper function to find the next smallest palindrome with an odd number of digits
    private String findSmallerPalindromeHelper(String n, int left, int right) {
        while (left >= 0 && n.charAt(left) == n.charAt(right)) {
            left--;
            right++;
        }
        
        // if we reached the end without finding a palindrome, then the next smallest palindrome will have one less digit
        if (left < 0) {
            return findSmallerPalindromeHelper(n, n.length() / 2 - 1, n.length() / 2);
        }
        
        // if we found a palindrome, then we need to see if we can make it smaller
        if (n.charAt(left) > n.charAt(right)) {
            // we can make the palindrome smaller by decrementing the left and right pointers
            return findSmallerPalindromeHelper(n, left - 1, right + 1);
        } else { // if we can't make the palindrome smaller, then we need to copy it over
            char[] arr = n.toCharArray();
            while (left >= 0) {
                arr[right] = arr[left];
                left--;
                right++;
            }
            return new String(arr);
        }
    }
    
    // helper function to find the next largest palindrome with an even number of digits
    private String findLargerPalindromeHelper(String n, int left, int right) {
        while (left >= 0 && n.charAt(left) == n.charAt(right)) {
            left--;
            right++;
        }
        
        // if we reached the end without finding a palindrome, then the next largest palindrome will have one more digit
        if (left < 0) {
            return findLargerPalindromeHelper(n, n.length() / 2, n.length() / 2 + 1);
        }
        
        // if we found a palindrome, then we need to see if we can make it larger
        if (n.charAt(left) < n.charAt(right)) {
            // we can make the palindrome larger by incrementing the left and right pointers
            return findLargerPalindromeHelper(n, left + 1, right - 1);
        } else { // if we can't make the palindrome larger, then we need to copy it over
            char[] arr = n.toCharArray();
            while (left >= 0) {
                arr[right] = arr[left];
                left--;
                right++;
            }
            return new String(arr);
        }
    }
    
    // helper function to find the next largest palindrome with an odd number of digits
    private String findLargerPalindromeHelper(String n, int left, int right) {
        while (left >= 0 && n.charAt(left) == n.charAt(right)) {
            left--;
            right++;
        }
        
        // if we reached the end without finding a palindrome, then the next largest palindrome will have one more digit
        if (left < 0) {
            return findLargerPalindromeHelper(n, n.length() / 2, n.length() / 2 + 1);
        }
        
        // if we found a palindrome, then we need to see if we can make it larger
        if (n.charAt(left) < n.charAt(right)) {
            // we can make the palindrome larger by incrementing the left and right pointers
            return findLargerPalindromeHelper(n, left + 1, right - 1);
        } else { // if we can't make the palindrome larger, then we need to copy it over
            char[] arr = n.toCharArray();
            while (left >= 0) {
                arr[right] = arr[left];
                left--;
                right++;
            }
            return new String(arr);
        }
    }
}

def find_the_closest_palindrome(num): 

# initialize a minimum difference to a very large number 
min_diff = float("inf") 

# convert the number to a string for easy manipulation 
num_str = str(num) 

# loop through all possible center positions for the potential palindrome 
for i in range(0, len(num_str)): 

    # for odd length palindromes, the center is at index i 
    # for even length palindromes, the center is between index i and i+1 
    for j in range(i, i + 2): 

        # form the left and right halves of the potential palindrome 
        # around the center 
        left = num_str[:i] 
        center = num_str[i:j] 
        right = num_str[j:] 

        # reverse the right half to form the mirror image 
        right = right[::-1] 

        # if the mirror image is the same as the left half, then 
        # we have found a palindrome 
        if left == right: 

            # the potential palindrome is of length 
            # 2*i + j - i (if j > i) or 2*i + j - i - 1 (if j <= i) 
            # convert it to an integer for comparison 
            potential_palindrome = int(left + center + right) 

            # update minimum difference if this palindrome is 
            # closer to the original number than the current 
            # minimum difference 
            if abs(potential_palindrome - num) < min_diff: 
                min_diff = abs(potential_palindrome - num) 

                # update the palindrome to return if this is the 
                # closest one so far 
                closest_palindrome = potential_palindrome 

    # return the closest palindrome 
    return closest_palindrome

/**
 * @param {string} n
 * @return {string}
 */
var nearestPalindromic = function(n) {
    // your code here
};

class Solution {
public:
    string nearestPalindromic(string n) {
        
        //find the length of the input string
        int len = n.length();
        
        //corner case:
        //if the input string is "1", the closest palindrome is "0"
        if(n == "1")
            return "0";
        
        //if the input string is a palindrome, we simply return the string itself
        if(is_palindrome(n))
            return n;
        
        //if the input string is not a palindrome, we need to find the next palindrome
        //there are three cases we need to consider:
        //1. the length of the next palindrome is the same as the input string
        //2. the length of the next palindrome is one digit longer than the input string
        //3. the length of the next palindrome is one digit shorter than the input string
        
        //case 1:
        //if the length of the next palindrome is the same as the input string
        //we simply need to find the next biggest number that is a palindrome
        //for example, if the input string is "125", the next biggest number is "131"
        //the steps to find the next biggest number is as follows:
        //1. we start from the middle digit and move to the left
        //2. if the digit is less than '9', we simply add 1 to the digit and return the result
        //3. if the digit is equal to '9', we set the digit to '0' and move to the next digit to the left
        //4. we repeat step 2 and 3 until we find a digit that is less than '9'
        //5. we add 1 to that digit and return the result
        
        string result = n;
        int mid = len/2;
        int i = mid - 1;
        int j = (len % 2)? mid + 1 : mid;
        
        bool leftsmaller = false;
        while(i >= 0 && n[i] == n[j])
            i--, j++;
        
        //if the left side is smaller, we simply need to make the left side equal to the right side
        if(i < 0 || n[i] < n[j])
            leftsmaller = true;
        
        while(i >= 0){
            result[i] = result[j] = (leftsmaller)? n[i] : ((n[i] > '0')? (char)(n[i] - 1) : '9');
            i--, j++;
        }
        
        //case 2:
        //if the length of the next palindrome is one digit longer than the input string
        //we simply need to find the next biggest number that is a palindrome
        //for example, if the input string is "1234", the next biggest number is "1331"
        //the steps to find the next biggest number is as follows:
        //1. we start from the middle digit and move to the left
        //2. if the digit is less than '9', we simply add 1 to the digit and return the result
        //3. if the digit is equal to '9', we set the digit to '0' and move to the next digit to the left
        //4. we repeat step 2 and 3 until we find a digit that is less than '9'
        //5. we add 1 to that digit and return the result
        
        //case 3:
        //if the length of the next palindrome is one digit shorter than the input string
        //we need to find the next smallest number that is a palindrome
        //for example, if the input string is "1235", the next smallest number is "1221"
        //the steps to find the next smallest number is as follows:
        //1. we start from the middle digit and move to the left
        //2. if the digit is greater than '0', we simply subtract 1 from the digit and return the result
        //3. if the digit is equal to '0', we set the digit to '9' and move to the next digit to the left
        //4. we repeat step 2 and 3 until we find a digit that is greater than '0'
        //5. we subtract 1 from that digit and return the result
        
        return result;
    }
    
    bool is_palindrome(string s){
        int i = 0;
        int j = s.length() - 1;
        
        while(i < j){
            if(s[i] != s[j])
                return false;
            i++;
            j--;
        }
        return true;
    }
};

using System; 

public class Solution {
    public string NearestPalindromic(string n) {
        // corner case
        if(n == "1") return "0";
        
        // generate candidates
        long num = long.Parse(n);
        List candidates = new List() {
            GetNextPalindrome(num + 1),
            GetNextPalindrome(num - 1),
            GetNextPalindrome(num),
            GetNextPalindrome(num + 2),
            GetNextPalindrome(num - 2)
        };
        
        // filter candidates
        candidates = candidates.Where(c => c != -1 && c != num).ToList();
        
        // get the closest one
        long closest = long.MaxValue;
        foreach(long c in candidates) {
            if(Math.Abs(num - c) < Math.Abs(num - closest)) {
                closest = c;
            }
        }
        
        return closest.ToString();
    }
    
    private long GetNextPalindrome(long num) {
        string s = num.ToString();
        int len = s.Length;
        int left = len / 2;
        int right = len % 2 == 0 ? left : left + 1;
        
        while(left >= 0 && right < len) {
            if(s[left] != s[right]) {
                return -1;
            }
            left--;
            right++;
        }
        
        return num;
    }
}