We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Closest Palindrome

Number: 564

Difficulty: Hard

Paid? No

Companies: Uber, Amazon, Microsoft, Goldman Sachs, Google, Oracle, Yelp

Problem Description

Given a string n representing an integer, return the closest integer (not including n itself) which is a palindrome. The “closest” is determined by the smallest absolute difference between the candidate palindrome and the given number. In the case of a tie, return the smaller palindrome.

Key Insights

  • The problem can be solved by generating a set of candidate palindromes rather than checking every integer.
  • One key idea is to mirror the first half of the string n to create a candidate and tweak the prefix (by decrementing and incrementing) to generate additional candidates.
  • Two edge candidates must be considered: one just below the power of 10 (e.g., 99, 999) and one just above (e.g., 1001, 10001) for numbers whose length may change when mirrored.
  • Exclude the candidate that is identical to the input number itself.
  • Finally, choose the candidate with the minimum absolute difference; in case of a tie, choose the numerically smaller one.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the input string (each candidate palindrome generation and comparisons operate on O(n) digits).
Space Complexity: O(n) for storing string slices and candidate palindromes.

Solution

We generate palindromic candidates using the “mirror” method on the first half of the number. First, extract the prefix formed by the first (len(n)+1)//2 digits and mirror it to generate a palindrome. To cover potential edge cases (such as changes in digit length), we also consider:

  • A candidate obtained by decrementing the prefix by 1 and mirroring.
  • A candidate obtained by incrementing the prefix by 1 and mirroring.
  • Two special candidates: one of the form 10^(length-1) - 1 (e.g., 99 for 3 digits) and another of the form 10^(length) + 1 (e.g., 1001 for 3 digits). We then remove the candidate equal to n, compute the absolute differences between the input number’s integer value and these candidates, and select the candidate with the smallest difference. In case of ties, the candidate with the smaller integer value is chosen.

Code Solutions

# Python Solution
def nearest_palindromic(n: str) -> str:
    length = len(n)
    num = int(n)
    candidates = set()
    
    # Edge-case candidates: 10^(len-1) - 1 and 10^(len) + 1
    candidates.add(10**(length - 1) - 1)
    candidates.add(10**length + 1)
    
    # Get the first half of the digits, rounding up for odd lengths.
    prefix = int(n[:((length + 1) // 2)])
    
    # Try three variations on the prefix: prefix, prefix-1, prefix+1
    for diff in (-1, 0, 1):
        new_prefix = str(prefix + diff)
        # If length is odd, exclude the last digit of the reversed new_prefix.
        if length % 2 == 0:
            pal_candidate = int(new_prefix + new_prefix[::-1])
        else:
            pal_candidate = int(new_prefix + new_prefix[:-1][::-1])
        candidates.add(pal_candidate)
        
    # Remove the original number itself, if present.
    candidates.discard(num)
    
    closest = None
    # Evaluate candidates based on absolute difference and then the smaller number.
    for candidate in candidates:
        if candidate < 0:
            continue
        diff = abs(candidate - num)
        if closest is None or diff < closest[1] or (diff == closest[1] and candidate < closest[0]):
            closest = (candidate, diff)
            
    return str(closest[0])

# Example usage:
print(nearest_palindromic("123"))  # Expected "121"
print(nearest_palindromic("1"))    # Expected "0"
← Back to All Questions