Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/564.html

564. Find the Closest Palindrome

Level

Hard

Description

Given an integer n, find the closest integer (not including itself), which is a palindrome.

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

Example 1:

Input: “123”

Output: “121”

Note:

  1. The input n is a positive integer represented by string, whose length will not exceed 18.
  2. If there is a tie, return the smaller one as answer.

Solution

For the given integer n, obtain the three closest palindromes, and find the closest palindrome among the three palindromes.

To obtain the three closest palindromes, first obtain the higher half of n. For example, for “123”, the higher half is “12”, and for “1024”, the higher half is “10”. The higher half can be considered as an integer. For the higher half, the higher half plus 1, and the higher half minus 1, generate the palindromes respectively.

One thing that needs to be paid attention to is when the higher half plus 1 has a longer length than the higher half or the higher half minus 1 has a shorter length than the higher half (including the case when the higher half minus 1 is 0). Examples are “990”, “10”, “1024”.

  • class Solution {
    public String nearestPalindromic(String n) {
        long[] nearestPalindromes = getNearestPalindromes(n);
        long num = Long.parseLong(n);
        long nearest = nearestPalindromes[0];
        long minDifference = Math.abs(num - nearest);
        int length = nearestPalindromes.length;
        for (int i = 1; i < length; i++) {
            long curPalindrome = nearestPalindromes[i];
            long difference = Math.abs(num - curPalindrome);
            if (difference > 0 && difference < minDifference) {
                nearest = curPalindrome;
                minDifference = difference;
            }
        }
        return String.valueOf(nearest);
    }

    public long[] getNearestPalindromes(String n) {
        int length = n.length();
        long min = (long) Math.pow(10, length - 1) - 1;
        long max = (long) Math.pow(10, length) + 1;
        int halfLength = (length + 1) / 2;
        String highHalfStr = n.substring(0, halfLength);
        long highHalf = Long.parseLong(highHalfStr);
        long[] nearestPalindromes = new long[3];
        nearestPalindromes[1] = generatePalindrome(highHalf, length);
        long prevHighHalf = highHalf - 1;
        int prevLength = prevHighHalf == 0 ? 0 : String.valueOf(prevHighHalf).length();
        if (prevLength == halfLength)
            nearestPalindromes[0] = generatePalindrome(prevHighHalf, length);
        else
            nearestPalindromes[0] = min;
        long nextHighHalf = highHalf + 1;
        int nextLength = String.valueOf(nextHighHalf).length();
        if (nextLength == halfLength)
            nearestPalindromes[2] = generatePalindrome(nextHighHalf, length);
        else
            nearestPalindromes[2] = max;
        return nearestPalindromes;
    }

    public long generatePalindrome(long highHalf, int length) {
        String highHalfStr = String.valueOf(highHalf);
        StringBuffer sb = new StringBuffer(highHalfStr);
        for (int i = length / 2 - 1; i >= 0; i--)
            sb.append(highHalfStr.charAt(i));
        return Long.parseLong(sb.toString());
    }
}

  • // OJ: https://leetcode.com/problems/find-the-closest-palindrome/
// Time: O(N)
// Space: O(N)
class Solution {
    string increment(string s) {
        int carry = 1, i = s.size() - 1;
        for (; i >= 0; --i) {
            carry += s[i] - '0';
            s[i] = carry % 10 + '0';
            carry /= 10;
        }
        if (carry) s.insert(begin(s), carry + '0');
        return s;
    }
    string decrement(string s) {
        int carry = -1, i = s.size() - 1;
        for (; i >= 0; --i) {
            carry += s[i] - '0';
            if (carry < 0) {
                s[i] = (carry + 10) % 10 + '0';
                carry = -1;
            } else {
                s[i] = carry % 10 + '0';
                carry /= 10;
            }
        }
        if (s.size() > 1 && s.front() == '0') s.erase(s.begin());
        return s;
    }
    string nextPalindrome(string &n) {
        auto half = n.substr(0, (n.size() + 1) / 2);
        string reverse(half.rbegin(), half.rend());
        if (lt(n.substr(n.size() / 2), reverse)) return half.substr(0, n.size() - reverse.size()) + reverse;
        auto first = increment(half);
        string second(first.rbegin(), first.rend());
        int len = n.size();
        if (first.size() > half.size()) ++len; // the length of the result will be n.size() + 1
        return first.substr(0, len - first.size()) + second;
    }
    string prevPalindrome(string &n) {
        if (n == "1") return "0";
        auto half = n.substr(0, (n.size() + 1) / 2);
        string reverse(half.rbegin(), half.rend());
        if (lt(reverse, n.substr(n.size() / 2))) return half.substr(0, n.size() - reverse.size()) + reverse;
        auto first = decrement(half);
        if (first.size() < half.size() || first == "0") return string(n.size() - 1, '9');
        string second(first.rbegin(), first.rend());
        return first.substr(0, n.size() - first.size()) + second;
    }
    string subtract(string a, string b) {
        string ans;
        int i = a.size() - 1, j = b.size() - 1, carry = 0;
        for (; i >= 0 && j >= 0; --i, --j) {
            carry += a[i] - b[j];
            if (carry >= 0) {
                ans.push_back(carry % 10 + '0');
                carry /= 10;
            } else {
                ans.push_back((carry + 10) % 10 + '0');
                carry = -1;
            }
        }
        while (ans.size() && ans.back() == '0') ans.pop_back();
        reverse(begin(ans), end(ans));
        return ans;
    }
    bool lt(string a, string b) {
        if (a.size() != b.size()) return a.size() < b.size();
        for (int i = 0; i < a.size(); ++i) {
            if (a[i] != b[i]) return a[i] < b[i];
        }
        return false;
    }
    bool le(string a, string b) { // returns true if a <= b
        if (a.size() != b.size()) return a.size() < b.size();
        for (int i = 0; i < a.size(); ++i) {
            if (a[i] != b[i]) return a[i] < b[i];
        }
        return true;
    }
public:
    string nearestPalindromic(string n) {
        auto a = nextPalindrome(n);
        auto b = prevPalindrome(n);
        return le(subtract(n, b), subtract(a, n)) ? b : a;
    }
};

  • class Solution:
    def nearestPalindromic(self, n: str) -> str:
        x = int(n)
        l = len(n)
        res = {10 ** (l - 1) - 1, 10**l + 1}
        left = int(n[: (l + 1) >> 1])
        for i in range(left - 1, left + 2):
            j = i if l % 2 == 0 else i // 10
            while j:
                i = i * 10 + j % 10
                j //= 10
            res.add(i)
        res.discard(x)

        ans = -1
        for t in res:
            if (
                ans == -1
                or abs(t - x) < abs(ans - x)
                or (abs(t - x) == abs(ans - x) and t < ans)
            ):
                ans = t
        return str(ans)

############

class Solution(object):
  def nearestPalindromic(self, n):
    """
    :type n: str
    :rtype: str
    """
    l = len(n)
    cands = set([str(10 ** l + 1), str(10 ** (l - 1) - 1)])
    prefix = int(n[:(l + 1) / 2])
    for half in map(str, [prefix - 1, prefix, prefix + 1]):
      cands.add(half + [half, half[:-1]][l & 1][::-1])
    cands.discard(n)
    return min(cands, key=lambda x: (abs(int(x) - int(n)), int(x)))


  • func nearestPalindromic(n string) string {
	l := len(n)
	res := []int{int(math.Pow10(l-1)) - 1, int(math.Pow10(l)) + 1}
	left, _ := strconv.Atoi(n[:(l+1)/2])
	for _, x := range []int{left - 1, left, left + 1} {
		y := x
		if l&1 == 1 {
			y /= 10
		}
		for ; y > 0; y /= 10 {
			x = x*10 + y%10
		}
		res = append(res, x)
	}
	ans := -1
	x, _ := strconv.Atoi(n)
	for _, t := range res {
		if t != x {
			if ans == -1 || abs(t-x) < abs(ans-x) || abs(t-x) == abs(ans-x) && t < ans {
				ans = t
			}
		}
	}
	return strconv.Itoa(ans)
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

All Problems

All Solutions