• Time:O(10^n)
• Space:O(1)

## C++

``````class Solution {
public:
int largestPalindrome(int n) {
if (n == 1)
return 9;

constexpr int kMod = 1337;
const int upper = pow(10, n) - 1;
const int lower = pow(10, n - 1) - 1;

for (int i = upper; i > lower; --i) {
const long cand = getPalindromeCandidate(i);
for (long j = upper; j * j >= cand; --j)
if (cand % j == 0)
return cand % kMod;
}

throw;
}

private:
long getPalindromeCandidate(int i) {
string reversed = to_string(i);
reverse(begin(reversed), end(reversed));
return stol(to_string(i) + reversed);
}
};
``````

## JAVA

``````class Solution {
public int largestPalindrome(int n) {
if (n == 1)
return 9;

final int kMod = 1337;
final int upper = (int) Math.pow(10, n) - 1;
final int lower = (int) Math.pow(10, n - 1) - 1;

for (int i = upper; i > lower; --i) {
final long cand = getPalindromeCandidate(i);
for (long j = upper; j * j >= cand; --j)
if (cand % j == 0)
return (int) (cand % kMod);
}

throw new IllegalArgumentException();
}

private long getPalindromeCandidate(int i) {
final String reversed = new StringBuilder().append(i).reverse().toString();
return Long.valueOf(i + reversed);
}
}
``````

## Python

``````class Solution:
def largestPalindrome(self, n: int) -> int:
if n == 1:
return 9

kMod = 1337
upper = pow(10, n) - 1
lower = pow(10, n - 1) - 1

for i in range(upper, lower, -1):
cand = int(str(i) + str(i)[::-1])
j = upper
while j * j >= cand:
if cand % j == 0:
return cand % kMod
j -= 1
``````