Java Solution using assumed max palindrom


  • 29
    C
            public int largestPalindrome(int n) {
            // if input is 1 then max is 9 
            if(n == 1){
                return 9;
            }
            
            // if n = 3 then upperBound = 999 and lowerBound = 99
            int upperBound = (int) Math.pow(10, n) - 1, lowerBound = upperBound / 10;
            long maxNumber = (long) upperBound * (long) upperBound;
            
            // represents the first half of the maximum assumed palindrom.
            // e.g. if n = 3 then maxNumber = 999 x 999 = 998001 so firstHalf = 998
            int firstHalf = (int)(maxNumber / (long) Math.pow(10, n));
            
            boolean palindromFound = false;
            long palindrom = 0;
            
            while (!palindromFound) {
                // creates maximum assumed palindrom
                // e.g. if n = 3 first time the maximum assumed palindrom will be 998 899
                palindrom = createPalindrom(firstHalf);
                
                // here i and palindrom/i forms the two factor of assumed palindrom
                for (long i = upperBound; upperBound > lowerBound; i--) {
                    // if n= 3 none of the factor of palindrom  can be more than 999 or less than square root of assumed palindrom 
                    if (palindrom / i > maxNumber || i * i < palindrom) {
                        break;
                    }
                    
                    // if two factors found, where both of them are n-digits,
                    if (palindrom % i == 0) {
                        palindromFound = true;
                        break;
                    }
                }
    
                firstHalf--;
            }
    
            return (int) (palindrom % 1337);
        }
    
        private long createPalindrom(long num) {
            String str = num + new StringBuilder().append(num).reverse().toString();
            return Long.parseLong(str);
        }
    

  • 2
    R

    I like the way you reverse the long, I did that way in an onsite interview. However, the interviewee ask me to implement it using the normal way, too. But I really like the StringBuilder.reverse(), I use it a lot.


  • 0
    R

    @rexue70 and is there any way to figure out the time complexity of that?


  • 0
    D
    This post is deleted!

  • 11
    L

    @chiranjeeb2 said in Java Solution using assumed max palindrom:

    palindrom / i > maxNumber

    Could you explain this line? Based on the comment, it seems that it should be It palindrom / i > upperBound. But then, just i * i < palindrom suffices?

    Also, the other part I can't wrap my head around is that although this seems to empirically work, how do we know that we will find a palindrome with 2n digits? For example, for n=2, 11 * 11 = 121 is a palindrome but has < 2n digits.

    Thanks!


  • 1
    A

    @lester.neo.leon said in Java Solution using assumed max palindrom:

    @chiranjeeb2 said in Java Solution using assumed max palindrom:

    palindrom / i > maxNumber

    Could you explain this line? Based on the comment, it seems that it should be It palindrom / i > upperBound. But then, just i * i < palindrom suffices?

    @lester-neo-leon yeah i think this would suffice as well -

            for (long i = upperBound; i * i >= palindrom; i--) {
                    if (palindrom / i <= lowerBound) {
                        break;
                    }
          ...
    

    One factor needs to be less than sqrt of palindrom (but greater than lowerbound )and the other greater.

    Also, the other part I can't wrap my head around is that although this seems to empirically work, how do we know that we will find a palindrome with 2n digits? For example, for n=2, 11 * 11 = 121 is a palindrome but has < 2n digits.

    Good point - I guess the solution assumes there will always be a 2n digit product palindrome. In any case, the loop breaks if one of the factors is less than lowerbound.


  • 0
    S

    public int largestPalindrome(int n) {
    int max=0;
    int min=0;
    int x, y;
    int reverse=0;
    for(int i=n-1; i>=0; i--)
    {
    max=max+(int)(9*(Math.pow(10,i)));
    }

        for(int i=max-1; i>0; i--)
        {
            reverse=0;
            min=i;
            x=max*min;
            y=x;
            
            while(y/10!=0)
            {
                reverse=reverse*10 + (y%10);
                y=y/10;
            }
            reverse=reverse*10+y;
            
            
            if(reverse == x)
            {
                int temp=x%1337;
                return temp;
            }
        }
        return min;
    }
    

    Guys this is my code and i have written it according to the problem statement however the output of my code varies with the actual output e.g. for n=3 my output is 1330 however the actual output is 123
    Can anybody tell me where am i wrong


  • 0
    M

    for (long i = upperBound; i * i >= palindrom; i--) {
    if (palindrom / i <= lowerBound) {
    break;
    }

    can somebody give me some examples? I can't understand this..


  • -3
    W

    I write a version more concise, just 4 lines

    public int largestPalindrome(int n) {
      if (n == 1) return 9;
      for (long max = (long) Math.pow(10, n) - 1, min = max / 10, half = max * max / (long) Math.pow(10, n);; half--)
        for (long i = max, palindrom = Long.parseLong(half + new StringBuilder(half + "").reverse().toString()); i > min && i * max >= palindrom && palindrom > min * i; i--)
          if (palindrom % i == 0) return (int) (palindrom % 1337);
    }

  • 7
    Y

    @chiranjeeb2 said in Java Solution using assumed max palindrom:

    for (long i = upperBound; upperBound > lowerBound; i--) {
    // if n= 3 none of the factor of palindrom can be more than 999 or less than square root of assumed palindrom
    if (palindrom / i > maxNumber || i * i < palindrom) {

    should be changed to:

    for (long i = upperBound; i > lowerBound; i--) {
    // if n= 3 none of the factor of palindrom can be more than 999 or less than square root of assumed palindrom
    if (palindrom / i > upperBound || i * i < palindrom) {

    Right?


  • 3
    Y

    @asanyal said in Java Solution using assumed max palindrom:

    Also, the other part I can't wrap my head around is that although this seems to empirically work, how do we know that we will find a palindrome with 2n digits? For example, for n=2, 11 * 11 = 121 is a palindrome but has < 2n digits.

    Good point - I guess the solution assumes there will always be a 2n digit product palindrome. In any case, the loop breaks if one of the factors is less than lowerbound.

    For n from 2 to 9, the largest palindromes are 2n digits. However, with the same algorithm, when n is 10 the palindrome returned is 18 digits, but it's possible that there is one larger palindrome which is with 19 digits.

    For n from 2 to 8 as noted by the question, the algorithm is safe.

    n = 2
    palindrom is: 9009
    number returned: 987

    n = 3
    palindrom is: 906609
    number returned: 123

    n = 4
    palindrom is: 99000099
    number returned: 597

    n = 5
    palindrom is: 9966006699
    number returned: 677

    n = 6
    palindrom is: 999000000999
    number returned: 1218

    n = 7
    palindrom is: 99956644665999
    number returned: 877

    n = 8
    palindrom is: 9999000000009999
    number returned: 475

    n = 9
    palindrom is: 999900665566009999
    number returned: 1226

    n = 10
    palindrom is: 461168600006861164
    number returned: 670


  • 1
    S
    This post is deleted!

  • 0
    D

    @sarvesh08 it is not the largest. That's 999x91. There ought to be a larger palindrome.


  • 3
    C

    thanks for sharing.
    The solution is based on the assumption that the palindrome can be created by concatenating 'firstHalf' and reversed 'firstHalf', thus it has even number of digits instead of odd number of digits. but how to prove that?


  • 0

    The idea of this question is greedy:

    1. find the max number that product of two number
    2. try first largest palindrome, then second ...
    3. verify if the palindrome can be formed by production of two i digit number.
    4. repeat this until the palindrome has been found.

  • 0
    This post is deleted!

  • 0
    N
    This post is deleted!

  • 0

    Nice solution! Just wonder why you are using

    if (palindrom / i > maxNumber || i * i < palindrom) {

    Change that like this also works

    if(palindrom/i > upperBound){


  • 0

    @coco007wind

    Good point. I would like to read the proof before being convinced. The following line to too hacky to understand.

    palindrom = createPalindrom(firstHalf);
    

  • 2
    G

    Simple version. Inspired by your code :)

    public int largestPalindrome(int n) {
        if(n == 1)  return 9;
        long maxNum = (long)Math.pow(10, n) - 1;
        long minNum = (long)Math.pow(10, n - 1);
        long maxProduct = maxNum * maxNum;
        long firstHalf = maxProduct / (long)Math.pow(10, n);
        
        while(true) {
            long candidate = palindrome(firstHalf--);
            if(candidate > maxProduct)  continue;
            // elinminate candidate like 9889,998899. Which generated from original firstHalf but larger than maxProduct
            for(long i = maxNum; i >= minNum; i--) {
                if(candidate / i > maxNum)  break;
                if(candidate % i == 0)  return (int) (candidate % 1337);
            }
        }
    }
    
    public long palindrome(long firstHalf) {
        String str = num + new StringBuilder().append(num).reverse().toString();
        return Long.parseLong(str);
    }

Log in to reply
 

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