Problem Statement
The problem gives us a string n which represents an integer. Our goal is to identify the closest integer (that is not the integer itself) that is also a palindrome. The term closest here implies the integer whose absolute difference with given n is minimal among all palindromic integers. In cases where there's a tie — when two palindromes are equidistant from n — we need to return the smaller palindrome.
Examples
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 <= 18nconsists of only digits.ndoes not have leading zeros.nis representing an integer in the range[1, 1018 - 1].
Approach and Intuition
Understanding a palindrome:
- A palindrome is a number that reads the same forward and backward. Examples are 121, 1331, and 3.
Steps to solve the problem:
- First, convert the string
nto an integer for numerical operations. - Search for palindromic numbers above and below the given integer, stopping once the closest palindrome has been identified.
- First, convert the string
Techniques to find palindromes:
- Generate palindromes numerically: Start from the integer represented by
n, and increment or decrement to find potential close palindromic numbers. - Mirroring technique: Utilize the first half of the number, mirror it, and check if the resulting number is a palindrome. Adjust as necessary based on closeness to
n.
- Generate palindromes numerically: Start from the integer represented by
Implementing tie-breaking:
- When two generated palindromes have the same absolute difference from
n, return the numerically smaller palindrome.
- When two generated palindromes have the same absolute difference from
The approach involves balanced operations with numbers up to 18 digits, due to the constraints given, ensuring that performance remains efficient. By leveraging simple number manipulation techniques and understanding the properties of palindromes, the algorithm efficiently pinpoints the nearest palindrome or palindromes to the integer n.
Solutions
- C++
- Java
- Python
class PalindromeFinder {
public:
long long makePalindrome(long long& value) {
string str = to_string(value);
int length = str.length();
int left = (length - 1) / 2, right = length / 2;
while (left >= 0) str[right++] = str[left--];
return stoll(str);
}
long long findPreviousPalindrome(long long val) {
long long start = 0, end = val;
long long result = INT_MIN;
while (start <= end) {
long long middle = (end - start) / 2 + start;
long long palindrome = makePalindrome(middle);
if (palindrome < val) {
result = palindrome;
start = middle + 1;
} else {
end = middle - 1;
}
}
return result;
}
long long findNextPalindrome(long long val) {
long long start = val, end = 1e18;
long long result = INT_MIN;
while (start <= end) {
long long middle = (end - start) / 2 + start;
long long palindrome = makePalindrome(middle);
if (palindrome > val) {
result = palindrome;
end = middle - 1;
} else {
start = middle + 1;
}
}
return result;
}
string closestPalindromic(string value) {
long long val = stoll(value);
long long prev = findPreviousPalindrome(val);
long long next = findNextPalindrome(val);
if (abs(prev - val) <= abs(next - val)) return to_string(prev);
return to_string(next);
}
};
This solution involves a C++ class, PalindromeFinder, designed to identify the closest palindrome number to a given input. The central part of this implementation is how palindromes are identified and evaluated in relation to the input value.
The class consists of several methods:
makePalindrome(long long& value): Converts a given number into its closest higher or equivalent palindrome by mirroring its digits around the center.
findPreviousPalindrome(long long val): Finds the largest palindrome less than or equal to a given value. It employs a binary search strategy between
0and the input value (val) to efficiently find the closest palindrome, using themakePalindromefunction to generate palindromes from the midpoints.findNextPalindrome(long long val): Locates the smallest palindrome greater than the given value. Similar to
findPreviousPalindrome, it uses binary search but starts from the input value and potentially goes up to1e18(10^18), adjusting the range based on the palindrome generated from the current midpoint.closestPalindromic(string value): This is the primary function to be called with a string representation of an integer. It converts the string to a
long long, obtains both the previous and next closest palindromes (if any), and then determines which palindrome is closer to the original input. In cases where both are equidistant from the input, the smaller palindrome (previous one) is chosen.
This class effectively encapsulates the logic for finding the closest palindrome numerically, address the needs for both decrementing and incrementing approaches through dedicated functions. This implementation ensures efficiency through binary search methods and string manipulation to create palindromes, suitable for large numbers given the upper bound constrained to 1e18.
class PalindromeUtil {
// Generate palindrome by mirroring the left half
private long mirrorLeftToRight(long number) {
String str = Long.toString(number);
int length = str.length();
int midIndex = (length - 1) / 2, rightIndex = length / 2;
char[] charArray = str.toCharArray();
while (midIndex >= 0) {
charArray[rightIndex++] = charArray[midIndex--];
}
return Long.parseLong(new String(charArray));
}
// Find the small palindrome less than the given number
private long findPreviousPalindrome(long val) {
long low = 0, high = val;
long result = Long.MIN_VALUE;
while (low <= high) {
long middle = (high - low) / 2 + low;
long mirrored = mirrorLeftToRight(middle);
if (mirrored < val) {
result = mirrored;
low = middle + 1;
} else {
high = middle - 1;
}
}
return result;
}
// Find the large palindrome greater than the given number
private long findNextPalindrome(long val) {
long low = val, high = (long) 1e18;
long result = Long.MIN_VALUE;
while (low <= high) {
long middle = (high - low) / 2 + low;
long mirrored = mirrorLeftToRight(middle);
if (mirrored > val) {
result = mirrored;
high = middle - 1;
} else {
low = middle + 1;
}
}
return result;
}
public String closestPalindrome(String n) {
long number = Long.parseLong(n);
long prevPalindrome = findPreviousPalindrome(number);
long nextPalindrome = findNextPalindrome(number);
if (Math.abs(prevPalindrome - number) <= Math.abs(nextPalindrome - number)) {
return Long.toString(prevPalindrome);
}
return Long.toString(nextPalindrome);
}
}
The solution provided in Java focuses on finding the closest palindrome number to a given number. It utilizes a combination of methods to generate palindromes and compare their proximity to the target number. Here’s how the process breaks down:
MirrorLeftToRight Method: This method generates a palindrome by mirroring the left half of the number to its right. It converts the number to a string, determines the middle, and copies characters from left to the mirror index on the right.
FindPreviousPalindrome Method: It searches for the largest palindrome that is smaller than the given number. It performs a binary search, using the
MirrorLeftToRightmethod to generate palindromes during each iteration, adjusting the search range based on whether the generated palindrome is less than the target value.FindNextPalindrome Method: Conversely, this method looks for the smallest palindrome larger than the given number, also utilizing a binary search mechanism in conjunction with the mirroring method. The search dynamically adjusts, narrowing down potential candidates based on their value relative to the target number.
ClosestPalindrome Method: This public method integrates the previous two methods to find both the next and previous closest palindromes to the input number. It compares these values relative to the original number and returns the palindrome that has the smallest absolute difference from the target number.
The solution effectively combines string manipulation, binary search, and numerical comparison to find the closest palindrome, emphasizing efficient searching and accurate mirroring techniques within the specified numerical constraints.
class Solution:
def makePalindrome(self, number: int) -> int:
num_str = str(number)
digits = len(num_str)
left_idx, right_idx = (digits - 1) // 2, digits // 2
num_list = list(num_str)
while left_idx >= 0:
num_list[right_idx] = num_list[left_idx]
right_idx += 1
left_idx -= 1
return int("".join(num_list))
def findPreviousPalindrome(self, number: int) -> int:
start, end = 0, number
best = float("-inf")
while start <= end:
middle = (end - start) // 2 + start
palindrome_num = self.makePalindrome(middle)
if palindrome_num < number:
best = palindrome_num
start = middle + 1
else:
end = middle - 1
return best
def findNextPalindrome(self, number: int) -> int:
start, end = number, int(1e18)
best = float("-inf")
while start <= end:
middle = (end - start) // 2 + start
palindrome_num = self.makePalindrome(middle)
if palindrome_num > number:
best = palindrome_num
end = middle - 1
else:
start = middle + 1
return best
def closestPalindromic(self, input_str: str) -> str:
input_num = int(input_str)
prev_pal = self.findPreviousPalindrome(input_num)
next_pal = self.findNextPalindrome(input_num)
if abs(prev_pal - input_num) <= abs(next_pal - input_num):
return str(prev_pal)
return str(next_pal)
The Python solution provided defines a way to find the closest palindrome number to a given integer. The solution involves several key functions within the Solution class to achieve this.
- The function
makePalindromeconverts a given number into its closest palindromic form by mirroring its digits around its center. - The function
findPreviousPalindromeidentifies the largest palindrome that is smaller than the given number. This is done using a binary search approach to efficiently narrow down the possible candidates. - Conversely, the
findNextPalindromelooks for the smallest palindrome greater than the provided number, also utilizing a binary search mechanism. - Using these helper functions, the main function
closestPalindromicaims to determine the closest palindrome, either smaller or larger, by comparing distances from the given number.
The logic here is implemented such that:
- Convert the provided string input to an integer.
- Leverage
findPreviousPalindrometo get the largest smaller palindrome. - Utilize
findNextPalindrometo fetch the smallest larger palindrome. - Compare which palindrome (previous or next) is closer in numerical distance to the original number.
- Return the closest palindrome as a string.
This approach balances efficiency and accuracy by narrowing potential candidates through binary search and ensures that the solution considers edge cases, where numbers may be quite close to very large palindromic values. Also, the implementation ensures that the base conversions between string and integer types are handled correctly for proper computation and output format.
No comments yet.