Java solution with detailed proof

• The basic idea for this problem is summarized in other posts (see awice's post), in which we will find a couple of candidate palindromes and choose the one that is closest to the given number. Here I will elaborate on this idea and show the theoretical proof behind the scene wherever possible.

`I -- The given number itself is a palindrome`

Since we are asked to find the closest palindrome, let's begin with the simple case when the given number itself is a palindrome.

Assume `n` is the string representation of the given number with length `m` (i.e., the number has `m` digits), `num` is the numerical value of `n`. Because `n` is a palindrome, we can break it into two parts from the middle: left part consisting of the first `p` digits and right part consisting of the remaining `k` digits, where `k = m/2` (integer division) and `p = m - k`. Note that in this definition, we have `p >= k`: the number of digits in the left part is no less than that in the right. Let `l` and `r` be the numerical values of the left and right parts, respectively. Then `num = l * 10^k + r`. To get a more concrete idea, let's work out an example. Suppose `n = "14241"`, then `m = 5`, `num = 14241`, `p = 3`, `k = 2`, `l = 142`, `r = 41` and apparently `num = l * 10^2 + r = 142 * 100 + 41 = 14241`.

Now assume we have another palindrome `n1` with length `m1` and numerical value `num1`. And again we will divide it into two parts, but instead breaking from the middle, we will break it such that the right part has `k1 = k` digits while the left part contains the remaining `p1 = m1 - k` digits. The corresponding numerical values of the left and right parts are `l1` and `r1` (if `m1 <= k`, all the digits go to the right part and we have `l1 = 0`). Similarly `num1 = l1 * 10^k + r1`. Again we take an example with `n1 = "131"`, then `m1 = 3`, `num1 = 131`, `p1 = 1`, `k1 = 2`, `l1 = 1`, `r1 = 31` and apparently `num1 = l1* 10^2 + r1 = 1 * 100 + 31 = 131`.

Next we will show that `l > l1 ==> num > num1`, that is if `l` is greater than `l1`, then the numerical value of `n` is greater than that of `n1`, i.e., `num > num1`. The proof is as follows. First note that `0 < r, r1 < 10^k`, which implies `|r - r1| < 10^k`. Second note that if `l > l1`, we have `l - l1 >= 1` since both of them are integers. Then `num - num1 = (l * 10^k + r) - (l1 * 10^k + r1) = (l - l1) * 10^k + (r - r1) >= 10^k + (r - r1) > 0`, that is `num > num1`. Similarly we can show that `l < l1 ==> num < num1`.

Now we will introduce a third palindrome `n2` with length `m2` and numerical value `num2`. Similar to `n1`, `n2` has left and right parts with numerical values `l2` and `r2`. We then can show that `l > l1 > l2 ==> d1 < d2`, where `d1 = abs(num - num1)` and `d2 = abs(num - num2)` denote the distances from `n1` and `n2` to `n`, respectively (`abs` means absolute values). The proof is rather straightforward. First from the conclusion above, we have `num > num1` and `num > num2`. Second by the same reasoning with `l`, `num` replaced by `l2`, `num2`, we conclude `l1 > l2 ==> num1 > num2`. Then `d1 - d2 = abs(num - num1) - abs(num - num2) = (num - num1) - (num - num2) = num2 - num1 < 0`. This is to say if we have two palindromes whose left part values are smaller than that of the given palindrome, then the one with larger left part value is closer to the given palindrome. Similarly we may show that `l < l1 < l2 ==> d1 < d2`, i.e., if we have two palindromes whose left part values are greater than that of the given palindrome, then the one with smaller left part value is closer to the given palindrome.

Since we are only concerned with the closest palindrome to `n`, our analyses above suggest we need to minimize the difference of the left part values between the candidate palindromes and `n`. Apparently the minimum difference we can get is `1` (it cannot be `0` otherwise the candidate palindrome is the same as `n`), and we end up with two candidate palindromes, one smaller than `n` and the other larger than `n`, both with left part values differ by `1` from that of `n`. We will denote these two candidate palindromes as `cn1` and `cn2`, with numerical values `cnum1` and `cnum2`, left part values `cl1` and `cl2`, and right part values `cr1` and `cr2`. We assume `cnum1 < num < cnum2`. Then `cl1` and `cl2` will be related to `l` by `cl1 = l - 1` and `cl2 = l + 1`.

Because `n` is given, `l` will be known to us. So the left parts of the two candidate palindromes will also be fixed. Then our task is equivalent to determining the whole palindrome from information of its left part. We will postpone this to the end of the post and move to the next part where the given number is not a palindrome.

`II -- The given number is a not palindrome`

We have shown how to find the candidate palindromes in part I, under the assumption that the given number `n` itself is a palindrome. But what if it is not?

Well, the answer to that is very simple: why don't we just go ahead and construct a palindrome from `n` by ourselves?

There are two ways of constructing a palindrome from `n`. First we divide it into two parts from the middle. Then we can either replace the left part with the reverse of the right, or replace the right part with the reverse of the left. If we replace the left part, the distance between the constructed palindrome to `n` is given by `abs(l - l') * 10^k`, where `l` and `l'` are the numerical values of the left parts of `n` and the constructed palindrome, respectively, since they share the right parts. However if we replace the right part, the distance will be `abs(r - r')`, where `r` and `r'` are the numerical values of the right parts of `n` and the constructed palindrome, respectively, as now they share the left parts. Apparently the former is greater than the latter, therefore the palindrome should be constructed by replacing the right part with the reverse of the left part.

Let `curP` be the palindrome constructed above, with numerical value `cur`. The two candidate palindromes built from `curP` as shown in part `I` are `preP` and `nextP`, with numerical values `pre` and `next`, respectively. Assuming `pre < cur < next`, we will show that `pre < num < next`, i.e., the numerical value of `n` itself is also in between `pre` and `next`.

The proof goes as follows. Let's assume the numerical values of the left and right parts of `n`, `preP`, `curP` and `nextP` are `l` and `r`, `l1` and `r1`, `l2` and `r2`, `l3` and `r3`, respectively. Since `curP` is constructed by replacing the right part only, we have `l2 = l`. Also from part `I`, we have `l1 = l2 - 1` and `l3 = l2 + 1`. Then `num - pre = (l * 10^k + r) - (l1 * 10^k + r1) = (l - l1) * 10^k + (r - r1) = 10^k + (r - r1) > 0` and `next - num = (l3 * 10^k + r3) - (l * 10^k + r) = (l3 - l) * 10^k + (r3 - r) = 10^k + (r3 - r) > 0`. Therefore `pre < num < next`.

Let `d1 = abs(num - pre)`, `d2 = abs(num - cur)` and `d3 = abs(num - next)`. The conclusion above means any palindrome smaller than `pre` or larger than `next` will have greater distance from `num` than at least one of `d1`, `d2` and `d3`, and thus cannot be the closest palindrome. Eventually the closest palindromes can only be one of `preP`, `curP` and `nextP`.

`III -- Construct the whole palindrome from its left part`

We have shown that the candidate palindromes can only be `preP`, `curP` and `nextP`. Obtaining `curP` is straightforward, by simply replacing the right part of `n` with the reverse of its left part. Obtaining `preP` and `nextP` requires some efforts since we only know the left parts for them.

To streamline our explanations below, let's first spell out the various notations for `preP`, `curP` and `nextP`: the number of digits are `m1`, `m2` and `m3`; the numerical values are `pre`, `cur` and `next`; the number of digits in the left part are `p1`, `p2` and `p3`; in the right part are `k1`, `k2` and `k3`; the numerical values of the left parts are `l1`, `l2` and `l3`; of the right parts are `r1`, `r2` and `r3`; respectively. Note the partition of the three palindromes are chosen such that `k2 = k/2, p2 = k - k2` where `k` is the number of digits in `n`, and `k1 = k2 = k3`, i.e., the three palindromes have the same number of digits in the right parts.

Next let's see how to work out `nextP`. From the analyses above, we have `l3 = l2 + 1`. If there is no carry beyond the most significant digit (MSD) of `l2`, then `p3 = p2`, which means `k3 = k/2, p3 = k - k3`. This implies `nextP` is also partitioned from the same middle position as `curP`. Therefore, the right part of `nextP` can be obtained by taking the last `k3` digits of the reverse of `l3`. If there is carry going on beyond MSD of `l2`, then `p3 = p2 + 1`. But this is only possible if all digits in `l2` is `9` and therefore `l3` will be of the form with a leading one followed by `p3` zeros. In this case, the right part of `nextP` can still be obtained by taking the last `k3` digits of the reverse of `l3`. So in either case, `nextP` can be obtained by attaching to its left part the string consisting of the last `k3` digits of the reverse of `l3`.

Lastly for `preP`, we have `l1 = l2 - 1`. Again, if there is no borrow from the MSD of `l2`, the right part of `preP` can be obtained by taking the last `k1` digits of the reverse of `l1`. However, there are two edge cases where `l2 = 1` and then `l1` becomes `0`: one is when `curP = "1"` and the other `curP = "11"`. The expression of `preP` for both cases can be readily known: `preP = "0"` for the former and `preP = "9"` for the latter. On the other hand, if there is borrow going on from the MSD of `l2`, then `l2` must be of the form with a leading one followed by `p2 - 1` zeros. As a result, all digits in `l1` will be `9`, and `k1 = k2 >= p2 - 1 = p1`. Since now the number of digits in `r1` is no less than that in `l1`, not only should we put all digits of the reverse of `l1` into `r1`, but also need to fill in the additional digit by hand in cases where `k1 > p1`. That additional digit can only be `9` if we want to minimize the distance from `preP` to `curP`.

It turns out that the algorithm for solving `preP` and `nextP` can be combined into one, as I did in the codes below. The function `nearestPalindrom` will return the closest palindrome to the input palindrome `curP`, and depending on whether `dir` is true or false, the returned palindrome will be greater or smaller than `curP`. The main function `nearestPalindromic` follows my analyses in part `II`, in which we first replace the right half of the given number `n` to construct the palindrome `curP`. We then call `nearestPalindrom` to build the two closest candidate palindromes from it. Lastly, out of the three candidates, we return the one that is closest to the given number (return the smaller one if there is a tie). Anyway, here are the codes for the two functions.

``````public String nearestPalindromic(String n) {
char[] arr = n.toCharArray();
for (int i = 0, j = arr.length - 1; i < j; i++, j--) arr[j] = arr[i];

String curP = String.valueOf(arr);
String preP = nearestPalindrom(curP, false);
String nextP = nearestPalindrom(curP, true);

long num = Long.valueOf(n);
long cur = Long.valueOf(curP);
long pre = Long.valueOf(preP);
long next = Long.valueOf(nextP);

long d1 = Math.abs(num - pre);
long d2 = Math.abs(num - cur);
long d3 = Math.abs(num - next);

if (num == cur) {
return d1 <= d3 ? preP : nextP;
} else if (num > cur) {
return d2 <= d3 ? curP : nextP;
} else {
return d1 <= d2 ? preP : curP;
}
}

private String nearestPalindrom(String curP, boolean dir) {
int k = curP.length() >> 1, p = curP.length() - k;
int l = Integer.valueOf(curP.substring(0, p));
l += (dir ? 1 : -1);

if (l == 0) return k == 0 ? "0" : "9";

StringBuilder left = new StringBuilder(String.valueOf(l));
StringBuilder right = new StringBuilder(left).reverse();
if (k > left.length()) right.append("9");

return left.append(right.substring(right.length() - k)).toString();
}
``````

• How do you construct the palindrome in step 2? Could you be more specific if taking "12345" as example please?

• @myyukiho Hi myyukiho. To turn `12345` into a palindrome, we can either reverse the left half (i.e. `12`) and replace the right half (i.e., `45`), so the number will be `12321`; or we can reverse the right half (i.e., `45`) and replace the left half (`12`) to get the number `54345`. But the number in the latter approach will have a larger distance from the original number `12345` than the number in the former approach, therefore we will take the former approach, that is "reverse the left half and replace the right half". (Note that for this example, the number of digits is odd so "half" does not include the middle digit.)

• @fun4LeetCode Thank you :)

• @fun4LeetCode My goodness. Apparently, not many people have the patience to read through this mostly-detailed written solution. I have to print it out. It is tough to read it on computer screen. Thanks though! Your solution is shorter than the one you cited at the beginning of your post.

• @wwzzgg Hi wwzzgg. You were right. I guess people hate those formulas highlighted in red/pink. Perhaps I should just paste the codes. LOL...

• not only should we put all digits of the reverse of l1 into r1, but also need to fill in the additional digit by hand in cases when k1 > p1

if (k > left.length()) right.append("9");

Great solution, thanks much for detailed explanation, I have started reading all your posts :O

Could you pls explain the above line ? why this is required ? I tried removing this line and tested with few examples which still yields the same result.

• @janarthanan Hello, janarthanan. The reason we need this line

``````if (k > left.length()) right.append("9");
``````

is to deal with test cases like `1000`, `1001`, ... (that is, `p == k` but the left part of the number is of the form `10^p`). For these test cases, when constructing `preP`, its left part will become shorter than `p` since there is borrow happening when subtracting `10^p` by `1`. Now if its right part is built by reversing its left part, the right part will be shorter than `k`, which will result in `java.lang.StringIndexOutOfBoundsException` when constructing the whole palindrome from the two parts.

• @fun4LeetCode thank you !!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.