Java two methods for using Long or String operations


  • 0

    Since the length of n is <= 18 so we can use Java long type to interpret the number and do +/- operation. I also provided pure String +/- methods so it could deal with even longer numbers.
    The basic idea is to find the smallest palindrome larger than n, and the biggest palindrome less than n and compare which one is closer to n. To get a larger palindrome we need add one to the prefix and to get a smaller palindrome we have to deduct one from the prefix. Pay attention to prefix = "9+" or "10*", in which case +/- 1 to the prefix will change its length.

       public static String nearestPalindromic(String n) {
            int len = n.length();
            if (len == 1) return n == "0" ? "1" : (n.charAt(0)-'0'-1)+"";
            String prefix = n.substring(0, (len+1)/2), suffix = new StringBuilder(n.substring(0, len/2)).reverse().toString();
            String p = prefix+suffix, prev = p, next = p;   //p is the palindrome by directly mirror the left half of the string
            long comp = Long.parseLong(n)- Long.parseLong(p);
            if (comp >= 0) {    //to find the smallest palindrome that's larger than n
                String newprefix = (Long.parseLong(prefix)+1)+"", newsuffix = new StringBuilder(newprefix.substring(0, newprefix.length()-len%2)).reverse().toString();
                next = newprefix+newsuffix;
                if (prefix.matches("9+")) { //in this case prefix+1 has one more bit than prefix so we need remove one bit
                    next = next.substring(0, next.length()/2)+next.substring(next.length()/2+1);
                }
            }
            if (comp <= 0) {    //to find the largest palindrome that's smaller than n
                if (prefix.matches("10*")) {    //in this case prefix-1 has one less bit than prefix so we need insert one bit
                    StringBuilder sb = new StringBuilder();
                    for (int i = 0; i < len-1; i++) sb.append("9");
                    prev = sb.toString();
                }
                else {
                    String newprefix = (Long.parseLong(prefix)-1)+"", newsuffix = new StringBuilder(newprefix.substring(0, newprefix.length()-len%2)).reverse().toString();
                    prev = newprefix+newsuffix;
                }
            }
            comp = (Long.parseLong(n)-Long.parseLong(prev)) - (Long.parseLong(next)-Long.parseLong(n));   //compare which one is shorter between go down and go up
            return comp <= 0 ? prev : next;
        }
    

    The code below provides string "+/-" operations which handles longer numbers:

        private int compare(String num1, String num2) { //compare two string represented number
            if (num1.length() > num2.length()) return 1;
            else if (num1.length() < num2.length()) return -1;
            for (int i = 0; i < num1.length(); i++) {
                if (num1.charAt(i) > num2.charAt(i)) return 1;
                else if (num1.charAt(i) < num2.charAt(i)) return -1;
            }
            return 0;
        }
        private String add(String num1, String num2) {  //string number addition
            StringBuilder sb = new StringBuilder();
            int i = num1.length()-1, j = num2.length()-1, carry = 0;
            while (i >= 0 || j >= 0 || carry != 0) {
                int a = i >= 0 ? num1.charAt(i--)-'0' : 0, b = j >= 0 ? num2.charAt(j--)-'0' : 0;
                sb.append((a+b+carry)%10);
                carry = (a+b+carry)/10;
            }
            return sb.reverse().toString();
        }
        private String deduct(String num1, String num2) {   //string number deduction
            if (compare(num1, num2) < 0) return null;
            StringBuilder sb = new StringBuilder();
            int i = num1.length()-1, j = num2.length()-1, borrow = 0;
            while (i >= 0) {
                int a = num1.charAt(i--)-'0', b = j >= 0 ? num2.charAt(j--)-'0' : 0;
                if (b+borrow > a) {
                    sb.append((10+a-b-borrow));
                    borrow = 1;
                } else {
                    sb.append(a-b-borrow);
                    borrow = 0;
                }
            }
            for (i = sb.length()-1; i > 0; i--) {
                if (sb.charAt(i) == '0') sb.deleteCharAt(i);
                else break;
            }
            return sb.reverse().toString();
        }
        public String nearestPalindromic(String n) {
            int len = n.length();
            if (len == 1) return n == "0" ? "1" : (n.charAt(0)-'0'-1)+"";
            String prefix = n.substring(0, (len+1)/2), suffix = new StringBuilder(n.substring(0, len/2)).reverse().toString();
            String p = prefix+suffix, prev = p, next = p;   //p is the palindrome by directly mirror the left half of the string
            int comp = compare(n, p);
            if (comp >= 0) {    //to find the smallest palindrome that's larger than n
                String newprefix = add(prefix, "1"), newsuffix = new StringBuilder(newprefix.substring(0, newprefix.length()-len%2)).reverse().toString();
                next = newprefix+newsuffix;
                if (prefix.matches("9+")) { //in this case prefix+1 has one more bit than prefix so we need remove one bit
                    next = next.substring(0, next.length()/2)+next.substring(next.length()/2+1);
                }
            }
            if (comp <= 0) {    //to find the largest palindrome that's smaller than n
                if (prefix.matches("10*")) {    //in this case prefix-1 has one less bit than prefix so we need insert one bit
                    StringBuilder sb = new StringBuilder();
                    for (int i = 0; i < len-1; i++) sb.append("9");
                    prev = sb.toString();
                }
                else {
                    String newprefix = deduct(prefix, "1"), newsuffix = new StringBuilder(newprefix.substring(0, newprefix.length()-1-len%2)).reverse().toString();
                    prev = newprefix+newsuffix;
                }
            }
            comp = compare(deduct(n, prev), deduct(next, n));   //compare which one is shorter between go down and go up
            return comp <= 0 ? prev : next;
        }
    

Log in to reply
 

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