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 ndigits,
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);
}
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, justi * 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!

@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, justi * i < palindrom
suffices?@lesterneoleon 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=n1; i>=0; i)
{
max=max+(int)(9*(Math.pow(10,i)));
}for(int i=max1; 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

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

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

@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: 987n = 3
palindrom is: 906609
number returned: 123n = 4
palindrom is: 99000099
number returned: 597n = 5
palindrom is: 9966006699
number returned: 677n = 6
palindrom is: 999000000999
number returned: 1218n = 7
palindrom is: 99956644665999
number returned: 877n = 8
palindrom is: 9999000000009999
number returned: 475n = 9
palindrom is: 999900665566009999
number returned: 1226n = 10
palindrom is: 461168600006861164
number returned: 670

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

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