Largest Palindrome Product
HardPrompt
Given an integer n, return the largest palindromic integer that can be represented as the product of two n-digits integers. Since the answer can be very large, return it modulo 1337.
Example 1:
Input: n = 2
Output: 987
Explanation: 99 x 91 = 9009, 9009 % 1337 = 987Example 2:
Input: n = 1
Output: 9
Constraints:
1 <= n <= 8
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves a straightforward brute-force search. It iterates through all possible pairs of n-digit numbers, starting from the largest ones. For each pair, it computes their product and checks if the product is a palindrome. It keeps track of the largest palindromic product found.
Algorithm
- Handle the base case where
n = 1, returning 9. - Determine the range of n-digit numbers. The upper bound is
upper = 10^n - 1and the lower bound is10^(n-1). - Initialize a variable
maxPalindrometo 0 to store the largest palindrome found. - Use a nested loop to iterate through all pairs of n-digit numbers. The outer loop for
iruns fromupperdown tolower. - The inner loop for
jruns fromidown tolowerto avoid duplicate products (i*jandj*i). - Inside the inner loop, calculate the product
p = i * j. - As an optimization, if
pis already smaller thanmaxPalindrome, we can break the inner loop because subsequent products for the currentiwill be even smaller. - Check if
pis a palindrome. This can be done by converting the number to a string and checking if it reads the same forwards and backward. - If
pis a palindrome, updatemaxPalindrome = p. - After the loops complete, return
maxPalindrome % 1337.
Walkthrough
The algorithm defines the range for n-digit numbers, which is from 10^(n-1) to 10^n - 1. It then uses two nested loops to explore all unique pairs of numbers within this range. To find the largest palindrome faster, the loops iterate downwards from the highest n-digit number.
For each product, a helper function isPalindrome is used to verify if it's a palindrome. If a palindromic product is found that is larger than the current maximum, the maximum is updated. A small optimization is included: since the inner loop also iterates downwards, if the current product becomes less than the largest palindrome found so far, we can break out of the inner loop, as no larger product can be found for the current outer loop iteration.
class Solution { public int largestPalindrome(int n) { if (n == 1) { return 9; } long upper = (long) Math.pow(10, n) - 1; long lower = (long) Math.pow(10, n - 1); long maxPalindrome = 0L; for (long i = upper; i >= lower; i--) { for (long j = i; j >= lower; j--) { long product = i * j; if (product < maxPalindrome) { // Since j is decreasing, further products for this i will also be smaller. break; } if (isPalindrome(product)) { maxPalindrome = product; } } } return (int) (maxPalindrome % 1337); } private boolean isPalindrome(long num) { String s = Long.toString(num); int len = s.length(); for (int i = 0; i < len / 2; i++) { if (s.charAt(i) != s.charAt(len - 1 - i)) { return false; } } return true; }}Complexity
Time
O(10^(2n)). The number of n-digit numbers is approximately `9 * 10^(n-1)`. The nested loops result in a complexity that is roughly the square of this number. This is computationally expensive and not feasible for the given constraints.
Space
O(n), where n is the number of digits. This space is used to store the string representation of the product, which can have up to 2n digits.
Trade-offs
Pros
Simple to understand and implement.
Guaranteed to find the correct answer.
Cons
Extremely inefficient for larger values of
n.Will result in a 'Time Limit Exceeded' error on most platforms for
n > 4.
Instead of checking every possible product, this more efficient approach generates palindromic numbers and then checks if they have two n-digit factors. By generating palindromes from largest to smallest, the first one that satisfies the condition is guaranteed to be the answer. This dramatically reduces the search space.
Algorithm
- Handle the base case where
n = 1, returning 9. - The largest palindrome product of two n-digit numbers will have
2ndigits (forn > 1). Such a palindrome is determined by its firstndigits (the 'left half'). - Calculate the upper bound for an n-digit number:
upper = 10^n - 1. - Iterate through possible left halves, from
upperdownwards. - For each
lefthalf, construct the full palindromep. For aleftvaluexyz, the palindrome isxyzyx. - Now, check if
pcan be factored into two n-digit numbers. Iterate a potential factorifromupperdownwards. - The search for
ican be optimized. We only need to checkidown tosqrt(p). Ifi < sqrt(p), the other factorp/iwould be larger thani, and we would have already encountered it as a potential factor. So, the inner loop condition isi * i >= p. - If
pis divisible byi(i.e.,p % i == 0), we have found a valid pair of n-digit factors (iandp/i). - Since we are generating palindromes from the largest possible downwards, the first one for which we find a valid factorization is the largest possible palindrome product.
- Return the result
p % 1337.
Walkthrough
This method is based on the observation that for n > 1, the largest palindrome formed by the product of two n-digit numbers will have 2n digits. A 2n-digit palindrome is symmetric, so it can be constructed from its first n digits (the 'left half').
The algorithm iterates through all possible n-digit left halves, starting from the largest (10^n - 1) and going downwards. For each left half, it constructs the full palindrome. For example, if n=3 and the left half is 998, the full palindrome is 998899.
Once a palindrome p is constructed, the algorithm checks if it's a product of two n-digit numbers. It does this by iterating a potential factor i from the largest n-digit number downwards. An important optimization is to stop the search for i when i * i < p. This is because if i were smaller than the square root of p, the other factor p/i would be larger than i, and we would have found the factorization when testing that larger factor.
Because we start with the largest possible palindromes, the first one we can factor into two n-digit numbers is our answer.
class Solution { public int largestPalindrome(int n) { if (n == 1) { return 9; } long upper = (long) Math.pow(10, n) - 1; // Iterate through the first half of the palindrome (left part) for (long left = upper; left > upper / 10; left--) { // Construct the full palindrome from the left part long p = createPalindrome(left); // Find a factor for this palindrome // The factor 'i' must be at most 'upper'. // We check i*i >= p because if i < sqrt(p), then the other factor p/i > sqrt(p), // and we would have found this pair when checking the larger factor. for (long i = upper; i * i >= p; i--) { if (p % i == 0) { // Found a factor. Since we iterate from the largest palindrome, // this is the largest palindrome product. return (int) (p % 1337); } } } return -1; // Should not be reached for n > 1 } private long createPalindrome(long num) { String s = Long.toString(num); String reversedS = new StringBuilder(s).reverse().toString(); return Long.parseLong(s + reversedS); }}Complexity
Time
O(10^n). The outer loop iterates through `O(10^n)` potential palindrome halves. The inner loop runs for a small number of iterations for the palindromes near the top of the range, as the factors will be close to the palindrome's square root. Therefore, the complexity is dominated by the outer loop.
Space
O(n), where n is the number of digits. This space is needed to create the string representation of the palindrome's left half.
Trade-offs
Pros
Significantly more efficient than brute-force.
Capable of solving the problem within the time limits for
nup to 8.
Cons
The logic is more complex than the brute-force approach.
It relies on the assumption that the largest palindrome has 2n digits, which holds for n > 1 but requires some mathematical insight.
Solutions
Solution
class Solution {public int largestPalindrome(int n) { int mx = (int)Math.pow(10, n) - 1; for (int a = mx; a > mx / 10; --a) { int b = a; long x = a; while (b != 0) { x = x * 10 + b % 10; b /= 10; } for (long t = mx; t * t >= x; --t) { if (x % t == 0) { return (int)(x % 1337); } } } return 9; }}class Solution: def largestPalindrome(self, n: int) -> int: mx = 10 ** n - 1 for a in range(mx, mx // 10, - 1): b = x = a while b: x = x * 10 + b % 10 b //= 10 t = mx while t * t >= x: if x % t == 0: return x % 1337 t -= 1 return 9class Solution {public: int largestPalindrome(int n) { int mx = pow(10, n) - 1; for (int a = mx; a > mx / 10; --a) { int b = a; long x = a; while (b) { x = x * 10 + b % 10; b /= 10; } for (long t = mx; t * t >= x; --t) if (x % t == 0) return x % 1337; } return 9; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.