# 479. Largest Palindrome Product

• Time: $O(10^n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 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(reversed.begin(), reversed.end()); return stol(to_string(i) + reversed); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 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); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 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