# Java Solution using assumed max palindrom

• ``````        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);
}
``````

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

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

• This post is deleted!

• 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!

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

• 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

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

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

• 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);
}``````

• 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?

• 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

• This post is deleted!

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

• 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?

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

• This post is deleted!

• This post is deleted!

• 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){

• @coco007wind

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

``````palindrom = createPalindrom(firstHalf);
``````

• 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);
}``````

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