564. Find the Closest Palindrome

Description

Given a string n representing an integer, return the closest integer (not including itself), which is a palindrome. If there is a tie, return the smaller one.

The closest is defined as the absolute difference minimized between two integers.

 

Example 1:

Input: n = "123"
Output: "121"

Example 2:

Input: n = "1"
Output: "0"
Explanation: 0 and 2 are the closest palindromes but we return the smallest which is 0.

 

Constraints:

• 1 <= n.length <= 18
• n consists of only digits.
• n does not have leading zeros.
• n is representing an integer in the range [1, 1018 - 1].

 

Solutions

Solution: Math

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {string} n
 * @return {string}
 */
const nearestPalindromic = function (n) {
  const { length } = n;
  const maxPalindrome = 10 ** length + 1;
  const minPalindrome = 10 ** (length - 1) - 1;
  const palindromes = [`${minPalindrome}`];
  const prefix = n.slice(0, Math.ceil(length / 2));
  const isOdd = length % 2;

  const createPalindrome = value => {
    value = `${value}`;
    const n = value.length;
    const start = isOdd ? n - 2 : n - 1;
    let result = value;

    for (let index = start; index >= 0; index--) {
      result += value[index];
    }
    return result;
  };

  for (let diff = -1; diff <= 1; diff++) {
    const value = +prefix + diff;
    const palindrome = createPalindrome(value);

    palindromes.push(palindrome);
  }
  palindromes.push(`${maxPalindrome}`);

  let result = maxPalindrome;
  let minDiff = Number.MAX_SAFE_INTEGER;

  for (const palindrome of palindromes) {
    if (palindrome === n) continue;
    const diff = Math.abs(palindrome - n);

    if (minDiff <= diff) continue;
    minDiff = diff;
    result = palindrome;
  }
  return result;
};