Java Solution with explanation


  • 25
    Z

    Hi there! I am sharing my solution. My idea is strightforward. First off, let's pay attention on some facts. Let's consider maximum number with n digits. Of course that is the number consisting only of digit 9 (999..9). Let's denote that number max, and consider max*max.

    • It is obvious that any number which is product of two n digit numbers is less than or equal to max*max.
    • Maximum possible length of the product is 2*n.
    • If we partition palindrome number into two equal halves, then left half must be equals to the reverse of the right half.

    Well, how to find the largest possible palindrome number? Answer: If max*max is palindrome itself, then that is the largest possible palindrome. Otherwise partition it into two equal(by length) halves. If left half is less than, or equals to the right half, then the largest palindrome number is concatenation of left part and reversed left part. Otherwise decrement left part, then find the largest palindrome as concatenation of left and reverse of it. Can we find next palindrome? Answer: yes. It is enough to repeat the latter operation, to obtain next largest palindrome. For example for input n = 2, max*max = 99*99 = 9801. So left half (further just left) is 98 and right half (further just right) is 01. 98>1, it mean largest palindrome is 9779. But it is not answer for our problem. Because this number is not product of two numbers with 2 digits. Well, to get valid palindromic number, we need to traverse all the palindromic numbers and check whether that number is a product of two numbers with n digits. To get the largest palindromic number, we have to approach the palindromic numbers greedily. It means, we need to traverse them from the largest to the smallest. Once we have found a palindrome, which is product of two n digital numbers return that number by mod 1337. That's all with the idea.
    Note the following points in implementation:

    • To optimally validate a palindrome number, (i.e whether it is product of two n digital numbers) use greedy approach. In other words, start from largest possible number until the number is greater than its pair. Because it prevents you from considering duplicate pairs. For instance, if a>b and a*b = pal, then no need to consider b*a = pal. It saves huge amount of time. Cope example:
           for(int i = max;i>pro/i;i--){
                   if(pro%i == 0 ) {
                       return (int)(pro%m);
                   }
            }
    
    • Do not forget to assign palindrome number ( pro in my case, which stands for product) long datatype. Because maximum possible palindrome consists of 16 digits, which is greater than Integer.MAX_VALUE.

    To sum up, I think this problem is NOT an EASY one. It would be better to tag it as MEDIUM.

    P.S: Sorry for dirty code.

    public class Solution {
        public int largestPalindrome(int n) {
            if(n == 1) return 9;
            int m = 1337;
            int mod = (int)Math.pow(10, n);
            int max = (int)Math.pow(10, n)-1;
            long pro = (long)max*(long)max;
            int right = (int)(pro%mod);
            int left = (int)(pro/mod);
            if(left == reverse(right,n)) return (int)(pro%m);
            if(left > right) {left--;}
            pro = (long)left*(long)mod+(long)reverse(left,n);
            while(left != mod/10){
                for(int i = max;i>pro/i;i--){
                    if(pro%i == 0 ) {
                        return (int)(pro%m);
                    }
                }
                left--;
                pro = (long)left*(long)mod+(long)reverse(left,n);
            }
            
            return (int)(pro%m);
        }
        
        private int reverse(int n, int dig){
            int x = n;
            int res = 0;
            int ten = (int)Math.pow(10,dig-1);
            while(x != 0 ){
                int d = x%10;
                res+=ten*d;
                ten/=10;
                x/=10;
            }
            return res;
        }
       
    }

  • 0
    M

    quite straightforward, but explanation is clear. thx


  • 0
    S

    Your explanation is quite clear. I think you had a typo in your code:
    if(left > pro) {left--} should be if(left>right) {left--};


  • 0
    Z

    @superplane Thanks, I have fixed


  • 0
    R

    said in Java Solution with explanation:

    while(left != mod/10){

    Hi,

    Could you explain why we are using left != mod/10 in while ?


  • 2
    Z

    Hi,@rsharsha! Here mod is 10^n. Well, we need palindromic number which is product of two n digit numbers. The mod/10 is the minimum number which consists of n digits. Therefore, there is no need to consider numbers that are less than mod/10. Moreover no need to consider mod/10 itself. Because, no positive number of n digits will give palindromic product with it. For instance, let's assume that n = 2. Then mod = 100, consequently mod/10 = 10. We can to stop searching once we have reached 10.


  • 0
    M

    very clear solution! Thank you!
    But I think this step:
    reverse(right,n);
    Is not necessary.


  • 2
    C

    I think your logic in this line if(left > right) {left--;} is totally wrong. You should compare left and reverse(right) but not left and right. Suppose pro = 9010, but the answer should be 9009. If you think left(90) > right(10) and you make left--, left will decrease to 89 and you will never get the correct answer 9009.

    I think you do not need this line of code.


  • 0
    A

    @ZhassanB Thanks for the solution. What would be the worst case time complexity?
    reverse takes O(n) time for each palindrome we try to build. So, can it be:
    (total number of palindromes with 2n digits) * (maximum number formed with n digit) * n(for reversal)?


  • 0
    Y

    What if "left < right < reversed(left)"? Seems that your initial pro will be greater than the upper bound?


  • 0
    T

    how about using right side instead of left, can we have a feasible solution ?. I am thinking about in case interviewer asks why we are decreasing left not right ?


  • 1
    Y

    @ZhassanB I think the procedure you mentioned of finding a largest palindrome has a little bit problem. Say, the number is 1923, the left part is 19 which is less than the right part 23, but the next largest palindrome is not 1991 but 1881. So I think the procedure can be modified to "If the reverse of the left part is less than or equal to the right part, then the concatenation of left part and reversed left part is the next largest palindrome; Otherwise, decrease the left part."
    But in this particular problem, it does not matter, since the multiple of 9..9 * 9..9 can always produce a number with both the left part and reversed left part are bigger than the right part.


Log in to reply
 

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