Java solution with detailed proof


  • 10
    F

    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();
    }
    

  • 0
    M

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


  • 0
    F

    @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.)


  • 0
    M

    @fun4LeetCode Thank you :)


  • 0
    W

    @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.


  • 0
    F

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


  • 0
    J

    @fun4LeetCode said in Java solution with detailed proof:

    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.


  • 0
    F

    @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.


  • 0
    J

    @fun4LeetCode thank you !!


Log in to reply
 

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