564. Find the Closest Palindrome

HardMathString

Problem Description

The problem asks for the closest integer to a given integer n, where the closest integer must be a palindrome. A palindrome is a number that reads the same backward as forward. We're not allowed to consider the integer n itself, and if there are two palindromes equally close to n, we must return the smaller one. The closeness between two integers is defined by the absolute difference between them, so we are looking for the integer with the minimum absolute difference from n that is also a palindrome.

Intuition

To find the closest palindrome, we can consider different cases. The following intuition helps us arrive at a solution:

The nearest palindrome could be smaller or larger than n: We must check in both directions.
Palindromes of different lengths can be candidates: For example, if n is a 3-digit number, then 99 and 1001 (palindromes just below and above the nearest 3-digit ones) might be closer than any other 3-digit palindrome.
We can focus on changing the first half of n: Any palindrome can be reflected by its first half. For example, to form palindromes near 12345, we could reflect 123 to form 12321, or change it slightly to 12221 (by reflecting 122) or 12421 (by reflecting 124).
There's no need to examine too many candidates: Because we're looking for the nearest palindrome, we only need to look at a very small range of numbers around n.
We pick the closest palindrome and resolve ties by choosing the smaller: This is done by comparing absolute differences and values directly.

The solution creates potential candidates by examining numbers formed by reflecting the digits around the center of n and by considering edge cases like 999->1001 (where all digits are 9). It then discards the original number n if it's already a palindrome and compares the remaining candidates to find the one with the minimum absolute difference to n.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of these pictures shows the visit order of a depth-first search?

I don’t know

Solution Approach

The provided solution uses algorithmic techniques and a logical approach to determine the nearest palindrome. Here's how the implementation tackles the problem:

First, the solution creates a set res to store potential palindromic numbers, including two edge cases:

10 ** (l - 1) - 1 which handles the case where the closest palindrome has one less digit and consists of all 9's (for example, 999 is the closest palindrome to 1000).
10**l + 1 which handles the case of a palindrome that has one more digit and starts and ends with a 1 (for example, 1001 is the closest palindrome to 999).

The int(n[: (l + 1) >> 1]) gets the first half of the digits (more precisely, the first half rounded-up if the length is odd, due to the >> 1 which is equivalent to dividing by 2 using bit shifting).

The loop for i in range(left - 1, left + 2): generates palindromes by considering the reflected versions of numbers just below, equal to, and just above the first half of n. The if l % 2 == 0 condition checks the length of n to decide on whether or not to consider the middle digit (for odd lengths) when creating the mirrored palindromes.

Within the loop, while j: is used to append the reversed digits of the first half to generate the full palindrome (i). Once complete, it adds these potential palindromes to the res set.

The line res.discard(x) ensures that the original number n is not considered if it is already a palindrome because the problem statement asks for a different number.

Finally, the solution iterates through the set res to find the candidate with the smallest absolute difference to x. It does this by considering both the difference and the value of t, using the abs() function to find the smallest absolute difference and resolve ties by choosing the smaller number.

In conclusion, the algorithm very efficiently narrows down the potential palindromes to consider and then picks the closest one by numerical comparison. By doing so, it avoids the brute force approach of checking each number in the range individually, which would be much less efficient.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Depth first search is equivalent to which of the tree traversal order?

Pre-order traversalPost-order traversalIn-order traversalLevel-order traversal

I don’t know

Example Walkthrough

Let's work through a small example using the number 123. According to the solution approach, our goal is to find the closest integer to 123 that is a palindrome, considering both smaller and larger potential palindromes.

First, we determine the length l of n. For 123, l is 3. We create a set res that we will use to store our potential palindrome candidates.

Now, we add our two edge cases to the set res:

10 ** (l - 1) - 1, which for 123 gives us 99 (the largest 2-digit palindrome).
10 ** l + 1, which for 123 gives us 1001 (the smallest 4-digit palindrome).

Next, we extract the first half of n. For 123, the first half (rounded up in the case of odd lengths) is 12. We will use this to generate palindromes that have the same first half as 123.

The solution then considers the numbers just below, equal to, and just above 12: these are 11, 12, and 13.

For each of these numbers, we generate a palindrome by mirroring the first half. For instance:

Mirroring 11 gives us 111.
Mirroring 12 (which is n’s exact first half) gives us 121.
Mirroring 13 gives us 131.

We add these palindromes to our set res. Now, res contains 99, 1001, 111, 121, and 131.

Since 123 is not a palindrome, we don't need to discard it from our set res. If 123 were a palindrome, we would remove it from the set since we are looking for a different integer.

Finally, we iterate through our set res to determine which number has the smallest absolute difference to 123. We calculate as follows:

abs(99 - 123) gives us 24.
abs(1001 - 123) gives us 878.
abs(111 - 123) gives us 12.
abs(121 - 123) gives us 2.
abs(131 - 123) gives us 8.

The smallest difference is 2 for the palindrome 121. Since we are asked to return the closest palindrome and in case of a tie return the smaller number, 121 is our answer as it is the closest palindrome to 123.

Solution Implementation

1class Solution:
2    def nearestPalindromic(self, n: str) -> str:
3        # Convert the string to an integer for numerical operations
4        num = int(n)
5        num_length = len(n)
6
7        # Initialize a set with the smallest and largest possible palindromes
8        # with different digit lengths compared to the input number
9        candidates = {
10            10**(num_length - 1) - 1,  # Smallest palindrome with one less digit
11            10**num_length + 1          # Smallest palindrome with one more digit
12        }
13
14        # Find the higher and lower palindromes around the input number
15        # 'prefix' is the first half of the input number
16        prefix = int(n[:(num_length + 1) // 2])
17
18        # Generate palindromes by varying the prefix by -1, 0, +1
19        for i in range(prefix - 1, prefix + 2):
20            # For even lengths, use the entire prefix.
21            # For odd lengths, exclude the last digit of the prefix.
22            j = i if num_length % 2 == 0 else i // 10
23
24            # Append the reverse of 'j' to 'i' to construct the palindrome
25            palindrome = i
26            while j > 0:
27                palindrome = palindrome * 10 + j % 10
28                j //= 10
29
30            # Add the constructed palindrome to the candidate set
31            candidates.add(palindrome)
32
33        # Remove the original number itself if it's in the set
34        candidates.discard(num)
35
36        # Find the closest palindrome to the original number
37        closest_palindrome = -1
38        for candidate in candidates:
39            # Check for the smallest absolute difference
40            # If the absolute difference is the same, choose the smaller number
41            if (closest_palindrome == -1 or
42                abs(candidate - num) < abs(closest_palindrome - num) or
43                (abs(candidate - num) == abs(closest_palindrome - num) and candidate < closest_palindrome)):
44                closest_palindrome = candidate
45
46        # Convert the closest palindrome back to a string and return
47        return str(closest_palindrome)
48

1class Solution {
2
3    // Function to find the nearest palindromic number in string form
4    public String nearestPalindromic(String n) {
5        // Convert the input string to a long integer for comparison
6        long number = Long.parseLong(n);
7
8        // Variable to store the closest palindrome number
9        long closestPalindrome = -1;
10
11        // Get all potential palindrome candidates
12        for (long candidate : getPalindromeCandidates(n)) {
13            // If this is the first candidate or it's closer to the input number than the current closest
14            // or equally close but smaller, then update the closest palindrome
15            if (closestPalindrome == -1 || 
16                Math.abs(candidate - number) < Math.abs(closestPalindrome - number) ||
17                (Math.abs(candidate - number) == Math.abs(closestPalindrome - number) && candidate < closestPalindrome)) {
18              
19                closestPalindrome = candidate;
20            }
21        }
22        // Convert the closest palindrome back to a string and return it
23        return Long.toString(closestPalindrome);
24    }
25
26    // Helper function to generate palindrome candidates based on the input string
27    private Set<Long> getPalindromeCandidates(String n) {
28        int length = n.length(); // Length of the input number
29        Set<Long> candidates = new HashSet<>(); // Set to store palindrome candidates
30      
31        // Add 9's (One less digit than n and all 9's) e.g. 999 for n=1000
32        candidates.add((long)Math.pow(10, length - 1) - 1);
33        // Add 1 followed by all zeros and then a 1 (One more digit than n) e.g. 10001 for n=999
34        candidates.add((long)Math.pow(10, length) + 1);
35
36        // Get the first half of n (if odd, include the middle digit)
37        long firstHalf = Long.parseLong(n.substring(0, (length + 1) / 2));
38        // Generate candidates by varying the first half from -1 to 1 and mirroring to get palindromes
39        for (long i = firstHalf - 1; i <= firstHalf + 1; ++i) {
40            StringBuilder candidateBuilder = new StringBuilder();
41            candidateBuilder.append(i); // Append the first half
42            // Mirror and append the reverse of the first half (excluding the middle digit if odd length)
43            candidateBuilder.append(new StringBuilder(Long.toString(i)).reverse().substring(length % 2));
44            // Add the generated number to candidates
45            candidates.add(Long.parseLong(candidateBuilder.toString()));
46        }
47
48        // Remove the number itself if it's a palindrome, as we want the nearest different palindrome
49        candidates.remove(Long.parseLong(n));
50      
51        return candidates; // Return the set of candidates
52    }
53}
54

1class Solution {
2public:
3    // Main function to find the nearest palindrome
4    string nearestPalindromic(string n) {
5        long originalNumber = stol(n); // Convert the original string to a long
6        long closestPalindrome = -1;   // Initialize the closest palindrome
7      
8        // Loop through all possible palindromes and choose the nearest one
9        for (long candidate : getCandidates(n)) {
10            if (closestPalindrome == -1 || 
11                abs(candidate - originalNumber) < abs(closestPalindrome - originalNumber) ||
12                (abs(candidate - originalNumber) == abs(closestPalindrome - originalNumber) && candidate < closestPalindrome)) {
13                closestPalindrome = candidate;
14            }
15        }
16        return to_string(closestPalindrome); // Return the string representation of the nearest palindrome
17    }
18
19    // Helper function to generate possible palindromes
20    unordered_set<long> getCandidates(string& n) {
21        int length = n.size();
22        unordered_set<long> candidates;
23      
24        // Add the edge cases: the largest number with one less digit and the smallest number with one more digit
25        candidates.insert((long) pow(10, length - 1) - 1);
26        candidates.insert((long) pow(10, length) + 1);
27      
28        // Get the first half of the original number and consider the number one less, one greater, and itself
29        long firstHalf = stol(n.substr(0, (length + 1) / 2));
30        for (long i = firstHalf - 1; i <= firstHalf + 1; ++i) {
31            string prefix = to_string(i); // First half as a string
32          
33            // Create a palindrome by appending the reverse of the prefix, considering odd/even length
34            string candidate = prefix + string(prefix.rbegin() + (length & 1), prefix.rend());
35          
36            // Add the generated palindrome to the set of candidates
37            candidates.insert(stol(candidate));
38        }
39      
40        // Remove the original number from the candidate set to ensure it's not considered as its own nearest palindrome
41        candidates.erase(originalNumber);
42      
43        return candidates; // Return the set of candidate palindromes
44    }
45};
46

1// Main function to find the nearest palindrome
2function nearestPalindromic(n: string): string {
3    const originalNumber: number = parseInt(n, 10); // Convert the original string to a number
4    let closestPalindrome: number = -1; // Initialize the closest palindrome
5
6    // Loop through all possible palindromes and choose the nearest one
7    for (const candidate of getCandidates(n)) {
8        if (closestPalindrome === -1 || 
9            Math.abs(candidate - originalNumber) < Math.abs(closestPalindrome - originalNumber) ||
10            (Math.abs(candidate - originalNumber) === Math.abs(closestPalindrome - originalNumber) && candidate < closestPalindrome)) {
11            closestPalindrome = candidate;
12        }
13    }
14    return closestPalindrome.toString(); // Return the string representation of the nearest palindrome
15}
16
17// Helper function to generate possible palindrome candidates
18function getCandidates(n: string): Set<number> {
19    const length: number = n.length;
20    const candidates: Set<number> = new Set<number>();
21
22    // Add the edge cases: the largest number with one less digit and the smallest number with one more digit
23    candidates.add(Math.pow(10, length - 1) - 1);
24    candidates.add(Math.pow(10, length) + 1);
25
26    // Get the first half of the original number and consider the number one less, one greater, and itself
27    const firstHalf: number = parseInt(n.substr(0, Math.ceil(length / 2)), 10);
28    for (let i: number = firstHalf - 1; i <= firstHalf + 1; i++) {
29        const prefix: string = i.toString(); // First half as a string
30      
31        // Create a palindrome by appending the reverse of the prefix, considering odd/even length
32        const reversedPrefix: string = prefix.split('').reverse().join('');
33        const candidateStr: string = prefix + reversedPrefix.substr(length % 2);
34      
35        // Add the generated palindrome to the set of candidates
36        candidates.add(parseInt(candidateStr, 10));
37    }
38
39    // Remove the original number from the candidate set to ensure it's not considered
40    // as its own nearest palindrome
41    candidates.delete(originalNumber);
42  
43    return candidates; // Return the set of candidate palindromes
44}
45

Not Sure What to Study? Take the 2-min Quiz：

Time and Space Complexity

Time Complexity

The time complexity of the given code can be broken down as follows:

Calculating res by adding the smallest and largest possible palindrome numbers around the length of n, which is O(1) since size of the res set remains constant regardless of the size of n.
Generation of near-by candidate palindromes involves constant time operations by iterating over a small range left - 1 to left + 2, which is O(1).
Constructing palindromes involves a while loop that iterates approximately l/2 times, where l is the length of n, resulting in O(len(n)) for each palindrome creation. Since we create at most three palindromes, the overall contribution is O(len(n)).
Discarding the original number x from the set res is also O(1) as it's a single operation.
The final for loop to choose the best palindrome candidate iterates over the elements in res. Since res has a maximum of 5 elements (fixed size), the loop runs in O(1) time.

Overall, summing these contributions, the time complexity of the code is primarily dependent on the length of n, leading to O(len(n)).

Space Complexity

The space complexity analysis is as follows:

A set res is created which holds at most 5 integers, thus contributing O(1) space.
Temporary variables such as x, l, left, i, j, ans, and t are all constant space overhead, adding up to O(1).

Therefore, the total space complexity of the code is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]["jm", "kn", "lo"]["jklmnp"]["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

564. Find the Closest Palindrome

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings