Clean Java solution that considers even and odd palindromes with explanation


  • 1
    C

    find max palindrome that is the product of two n-digit factors

    n___ factor range____ palindrome range
    2 10..99 100..9801
    3 100..999 10000..998001
    4 1000..9999 1000000..99980001

    ...

    there are odd length palindromes e.g. 191 and even length palindromes e.g. 9779. In this problem both are possible, but the even are more likely because the largest is required and there are many even before the first odd comes.

    Two ways to find palindromes that are products of n-digit integers:

    1. create all products with possible factors and check if the product is a palindrome. The problem is the order of the products which requires space and adds complexity. I didn't follow this further.
    2. create palindromes in decreasing order and check if it can be created by the multiplication of two factors with given range. There will be roughly 10^n such palindromes. Checking whether such a number is the product of two n-digit integers requires trying dividing that palindrome approx. its square root times. But there are limits on the numbers that heavily reduce work:
      • avoid double checking e.g. 19 = 91: iterate only from 1 to 9^(1/2) (square root of 9)
      • if e.g. the number can't be greater than 9, do not try 9*x < palindrome --> min-to-try = ceiling(palindrome / 9)
    public int largestPalindrome(int n) {
        if(n < 1 || n > 8) throw new IllegalArgumentException();
    
        long factMin = (long)Math.pow(10, n - 1); // e.g. 10^(3-1) = 100
        long factMax = factMin * 10 - 1; // e.g. 100*10 - 1 = 999
    
        for(long left = factMax * factMax / (factMin * 10); left >= factMin; left--) {
            long palindrome = createEvenPalindrome(left);
            if(findProduct(palindrome, factMin, factMax) != 0)
                return (int)(palindrome%1337L);
        }
    
        for(long left = factMin * 10 - 1; left >= factMin; left--) {
            long palindrome = createOddPalindrome(left);
            if(findProduct(palindrome, factMin, factMax) != 0)
                return (int)(palindrome%1337L);
        }
    
        return 0;
    }
    
    // returns x so that product % x == 0 or 0 if no x exists. 
    // x must be in the inclusive range [factMin, factMax]
    static private long findProduct(long product, long factMin, long factMax) {
        factMin = Math.max((product + factMax - 1) / factMax, factMin); // max(ceiling(product / factMax), factMax)
        factMax = Math.min((long)Math.sqrt((double)product), factMax);
        for(long mul = factMin; mul <= factMax; mul++) {
            if(product % mul == 0) return mul;
        }
        return 0;
    }
    
    // creates an even palindrome by mirroring the given part on the right.
    // e.g. left = 123 --> return 123321
    static private long createEvenPalindrome(long left) {
        long palindrome = left;
        for(; left > 0; left /= 10)
            palindrome = palindrome * 10L + (left % 10);
        return palindrome;
    }
    
    // creates an odd palindrome e.g. 123 --> 12321
    static private long createOddPalindrome(long left) {
        long palindrome = left;
        for(left /= 10; left > 0; left /= 10)
            palindrome = palindrome * 10L + (left % 10);
        return palindrome;
    }
    

Log in to reply
 

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