Largest Palindrome Product solution and explanation
7 more videos on this problem
【每日一题：小Fu讲解】LeetCode 479. Largest Palindrome Product傅码爷 · 17:01 · 1K views
Leetcode 479 Largest Palindrome ProductMath Geeks · 5:01 · 750 views
【每日一题】479. Largest Palindrome Product, 6/26/2021Huifeng Guan · 11:41 · 544 views
Largest Palindrome Product - Leetcode [ Darija]0xkernel · 9:37 · 89 views
No Sound Leetcode 479: Largest Palindrome ProductExtremeProgrammer · 2:12 · 51 views
Leetcode 0479. Largest Palindrome ProductFearless Learner · 11:23 · 34 views
LeetCode 479: Largest Palindrome ProductAlitaCode · 29:36 · 28 views
Chatgpt C++ leetcode 479. Largest Palindrome ProductWindows 8.1 Tails Prower Ultra · 3:28 · 11 views
The problem
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 = 987
Example 2:
Input: n = 1 Output: 9
Constraints:
1 <= n <= 8
Approach overview
Problem Overview: Given an integer n, find the largest palindrome made from the product of two n-digit numbers. The result must be returned modulo 1337. A brute force search works for small ranges, but smarter enumeration of palindromes reduces the search space significantly.
Approach 1: Brute Force with Optimization (Time: O(10^(2n)), Space: O(1))
Start from the largest n-digit number (10^n - 1) and iterate downward for both multiplicands. For each pair (i, j), compute the product and check whether the number is a palindrome by reversing its digits or converting it to a string. To reduce work, break the inner loop once the product drops below the best palindrome already found. Another small optimization is iterating j from i downward to avoid duplicate pairs. This approach relies on straightforward enumeration and palindrome checking, which fits naturally under enumeration and math techniques.
Approach 2: Constructing Palindromes First (Time: ~O(10^n), Space: O(1))
Instead of testing every product, generate palindrome candidates directly. Take a number representing the first half of the palindrome, mirror it to form a full palindrome, then check whether it can be factored into two n-digit numbers. For each generated palindrome p, iterate possible divisors from the largest n-digit value downward and check p % d == 0. If the complementary factor p / d also has n digits, the palindrome is valid. Because palindromes are generated in descending order, the first valid one is the largest. This approach drastically reduces the number of candidates compared with brute force and is the standard optimization using enumeration combined with numeric symmetry.
Recommended for interviews: Interviewers expect the palindrome-construction approach. Starting with brute force shows you understand the search space and basic palindrome checking. Switching to generating palindromes first demonstrates deeper reasoning about number symmetry and reduces the search from checking millions of products to testing a small set of structured candidates.
Approach 1: Brute Force with Optimization
This method involves calculating the product of all pairs of two n-digit numbers and checking which of these products is a palindrome. We start from the largest possible two n-digit numbers and work our way down, allowing us to find the maximum palindrome early in the looping process. Stop iterating early if the palindrome has been discovered.
def largest_palindrome(n):
if n == 1:
return 9
upper_limit = 10**n - 1
lower_limit = 10**(n-1)
max_palindrome = 0
for i in range(upper_limit, lower_limit - 1, -1):
for j in range(i, lower_limit - 1, -1):
product = i * j
if product <= max_palindrome:
break
if str(product) == str(product)[::-1]:
max_palindrome = product
return max_palindrome % 1337
print(largest_palindrome(2))public class Solution {
public int largestPalindrome(int n) {
if (n == 1) return 9;
int upperLimit = (int)Math.pow(10, n) - 1;
int lowerLimit = (int)Math.pow(10, n-1);
int maxPalindrome = 0;
for (int i = upperLimit; i >= lowerLimit; i--) {
for (int j = i; j >= lowerLimit; j--) {
int product = i * j;
if (product <= maxPalindrome) break;
if (isPalindrome(product)) {
maxPalindrome = product;
}
}
}
return maxPalindrome % 1337;
}
private boolean isPalindrome(int number) {
int original = number, reverse = 0;
while (number != 0) {
reverse = reverse * 10 + number % 10;
number /= 10;
}
return original == reverse;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.largestPalindrome(2));
}
}public class Solution {
public int LargestPalindrome(int n) {
if (n == 1) return 9;
int upperLimit = (int)Math.Pow(10, n) - 1;
int lowerLimit = (int)Math.Pow(10, n-1);
int maxPalindrome = 0;
for (int i = upperLimit; i >= lowerLimit; i--) {
for (int j = i; j >= lowerLimit; j--) {
int product = i * j;
if (product <= maxPalindrome) break;
if (IsPalindrome(product)) {
maxPalindrome = product;
}
}
}
return maxPalindrome % 1337;
}
private bool IsPalindrome(int num) {
int original = num, reversed = 0;
while (num != 0) {
reversed = reversed * 10 + num % 10;
num /= 10;
}
return original == reversed;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.LargestPalindrome(2));
}
}The solution iterates through potential n-digit number pairs in a descending order of magnitude, calculating their product and checking if it's a palindrome. By doing this in a descending order, the first palindrome found is the largest possible, thus shortening the loop cycles once it's discovered. The result is then taken modulo 1337 as required by the problem statement.
Time Complexity: O((10^n)^2) in the worst case, due to the nested iterations over n-digit numbers.
Space Complexity: O(1), as no additional space is used beyond integer storage.
Approach 2: Constructing Palindromes First
Rather than exploring the entire solution space of n-digit number pairs, this approach first constructs palindromic numbers, then checks their composability as products of two n-digit numbers. By constructing palindromes directly, we constrain the problem, focusing directly on known feasible solutions.
def largest_palindrome(n):
if n == 1:
return 9
upper_limit = 10**n - 1
lower_limit = 10**(n-1)
max_palindrome = 0
for i in range(upper_limit, upper_limit // 10, -1):
s = str(i)
palin = int(s + s[::-1])
for j in range(upper_limit, lower_limit - 1, -1):
if j * j < palin:
break
if palin % j == 0 and lower_limit <= palin // j <= upper_limit:
max_palindrome = palin
return max_palindrome % 1337
return max_palindrome % 1337
print(largest_palindrome(2))This Python code constructs palindromes from large numbers down by appending reverse digits to form potential products. It then checks for composability as a product of two n-digit numbers, breaking early to optimize time when a solution is found.
Time Complexity: O(10^n), where number of palindrome candidates is reduced compared to complete n-digit multiplicands.
Space Complexity: O(1).
Approach 3: Default Approach
class 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;
}
};func largestPalindrome(n int) int {
mx := int(math.Pow10(n)) - 1
for a := mx; a > mx/10; a-- {
x := a
for b := a; b != 0; b /= 10 {
x = x*10 + b%10
}
for t := mx; t*t >= x; t-- {
if x%t == 0 {
return x % 1337
}
}
}
return 9
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force with Optimization | Time Complexity: O((10^n)^2) in the worst case, due to the nested iterations over n-digit numbers. |
| Constructing Palindromes First | Time Complexity: O(10^n), where number of palindrome candidates is reduced compared to complete n-digit multiplicands. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Optimization | O(10^(2n)) | O(1) | Useful for understanding the search space or when n is very small |
| Constructing Palindromes First | ~O(10^n) | O(1) | Best practical solution; drastically reduces candidates by generating palindromes directly |
Frequently asked questions
Is Largest Palindrome Product easy or hard?
Largest Palindrome Product is rated Hard on LeetCode because the straightforward brute force approach is too slow for larger inputs. The challenge lies in recognizing the symmetry of palindromes and generating them efficiently before checking valid factors.
Largest Palindrome Product Python/Java solution
Python and Java implementations usually follow the palindrome-construction approach: generate a mirrored palindrome from a prefix, then check divisibility by n-digit numbers. The first valid palindrome found is returned modulo 1337 as required by the problem.
How to solve Largest Palindrome Product in O(n)?
A strict O(n) solution does not exist because the algorithm must explore multiple candidate palindromes and divisors. The practical optimization is generating palindromes first and checking divisibility by n-digit numbers, which reduces the effective complexity to roughly O(10^n) rather than enumerating every product.
What is the best approach for Largest Palindrome Product?
The most effective approach constructs palindrome numbers first, then checks whether they can be factored into two n-digit numbers. Generating palindromes in descending order guarantees the first valid match is the largest. This avoids checking every possible product and significantly reduces the search space.
Is Largest Palindrome Product asked at Google/Amazon/Meta?
Palindrome and numeric enumeration problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of this problem test understanding of number properties, optimization of brute force searches, and mathematical pattern recognition.
What data structure is used in Largest Palindrome Product?
The problem primarily uses mathematical operations and enumeration rather than complex data structures. Integer arithmetic, digit reversal, and divisor checks are the key operations used to generate and validate palindrome candidates.
What is the time complexity of Largest Palindrome Product?
A naive brute force approach takes roughly O(10^(2n)) time because it tests every pair of n-digit numbers. The optimized palindrome-construction approach reduces this to about O(10^n) candidate checks, making it far more practical for the constraint n ≤ 8.