479. Largest Palindrome Product
Problem Description
Given an integer n
, the task is to find the largest palindromic integer that can be obtained by multiplying two n
-digit numbers. A palindromic number is one that remains the same when its digits are reversed, such as 12321 or 45654. Since the resulting palindromic number could be quite large, the problem requires the final solution to be presented modulo 1337
. This means you should take the remainder after dividing the palindromic number by 1337
before returning it. When n = 1
, the largest palindromic number that can be formed is simply 9 (which is the product of two 1-digit numbers: 3 * 3), so the function returns 9.
Intuition
To find the largest palindromic integer product of two n
-digit numbers, we start from the maximum n
-digit number possible, mx = 10^n - 1
, and decrement from there. This is because we are interested in the largest possible product, which means we should start multiplying from the largest n
-digit numbers.
The algorithm constructs the palindromic number by appending the reverse of the left half to itself. This ensures that the number is palindromic. We initiate b
with the value of a
and x
as a
, then extend x
to be the full palindromic number by repeatedly multiplying x
by 10 (to shift digits to the left) and then adding the last digit of b
to x
after which b
is divided by 10 (effectively dropping the last digit of b
).
After constructing the palindromic number x
, we try to find a divisor t
that is a maximum n
-digit number such that x % t == 0
. If such a t
exists, then x
is a product of two n
-digit numbers and we return x % 1337
as the result. We only need to check divisors down to the square root of x
because if x
is divisible by some number greater than its square root, the corresponding factor would have to be less than the square root of x
, which we would already have checked.
If a palindromic number cannot be found with the current a
, the algorithm decrements a
and tries again, continuing to loop over descending n
-digit numbers until it finds a palindromic product. If n
is 1, the loop doesn't need to run since the only 1-digit palindromic product is 9, so in this case the algorithm returns 9.
Learn more about Math patterns.
Solution Approach
The implementation uses a single for
loop to iterate over all possible n
-digit numbers, starting from the largest (mx = 10^n - 1
) and decrementing to the lowest possible n
-digit number, which is 10^(n-1)
. Since we're interested in the largest palindromic product, we do not need to check any numbers less than mx // 10
.
For each iteration:
-
We initialize
b
to the value ofa
andx
toa
as well. Then, we construct a palindromic numberx
by reversing the digits ofa
and appending them to the originala
. This is done within awhile
loop — each time we take the last digit ofb
usingb % 10
, append it tox
by multiplyingx
by10
and adding this last digit, and remove the last digit fromb
using integer divisionb //= 10
. -
We then initialize another temporary variable
t
, also with the value ofmx
, and perform anotherwhile
loop with the conditiont * t >= x
. This allows us to check ifx
is divisible (x % t == 0
) by anyn
-digit numbert
. If it is, that meansx
is a palindromic product of twon
-digit numbers and we returnx % 1337
. The conditiont * t >= x
works because if no factor is found beforet
reaches√x
, thenx
cannot have twon
-digit factors — it would require one factor to be smaller thann
digits. -
The loop decrements
t
after every iteration. If no divisor is found for the current palindromic numberx
, the outer loop decreases the value ofa
, hence trying with a new, smallern
-digit number. -
If there's no palindromic number found for
n > 1
, the algorithm will naturally exit thefor
loop. This does not occur for anyn > 1
as per the problem's constraints. However, ifn = 1
, then the function directly returns9
, as this is the only single-digit palindromic number product (sincen
-digit numbers in this case are between1
and9
).
The key to this solution is the efficient construction of palindromic numbers and the expedited search for divisors starting from the largest possible n
-digit number.
No additional data structures are used apart from a few variables to store intermediate values and the result. The implementation makes use of simple arithmetic operations and loops to achieve the outcome.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with an example where n = 2
. This means we are looking for the largest palindromic number that can be obtained by multiplying two 2-digit numbers.
-
The maximum 2-digit number is
99
(mx = 10^n - 1
, withn
being 2 in this case, so10^2 - 1 = 100 - 1 = 99
). -
We start with
a = mx
, which is99
in this example, and try to construct a palindromic number usinga
. We initializeb
toa
(b = 99), andx
toa
(sox
is also99
initially). -
To create the palindromic number, we need to append the reverse of
b
tox
. Sinceb = 99
, we take the last digit ofb
byb % 10
, which is9
, multiplyx
by 10 to make space for the new digit, and add9
tox
. After this,b
is divided by 10 to drop the last digit (b becomes 9). We repeat this untilb
becomes 0, finishing withx
as the palindromic numberx = 9999
. -
Now, we want to see if this palindromic number
9999
is a product of two 2-digit numbers. We initialize a temporary variablet
with the value ofmx
(t = 99
), and check ifx
is divisible byt
whilet * t >= x
. -
So, we check if
9999 % 99 == 0
. This is not the case, so we decrementt
by 1 and check again. -
We continue this process, testing each
t
(98, 97, 96, ..., until we findx % t == 0
). If we find such at
, we would then returnx % 1337
. -
However, for this example, we will eventually find that no such
t
exists forx = 9999
. Therefore, we decrementa
and start over.a
becomes98
, and we repeat the above steps to construct a new palindromic numberx = 9889
and search again for a divisort
. -
Eventually, we'll construct the palindromic number
x = 9009
(froma = 91
), and we'll find out that it is divisible byt = 99
(since9009 % 99 == 0
). -
Once the valid
t
is found, we takex % 1337
to find the result modulo1337
. Forx = 9009
, the result is9009 % 1337
, which equals123
.
In this example walkthrough, the function would return 123
as the largest palindromic number that can be obtained by multiplying two 2-digit numbers modulo 1337
.
Solution Implementation
1class Solution:
2 def largestPalindrome(self, n: int) -> int:
3 # Define the maximum value for the given digit count.
4 max_num = 10**n - 1
5
6 # Loop backwards from the maximum number to find the largest palindrome.
7 # Stop at a reduced max_num (maximum divided by 10), to not check smaller sizes.
8 for first_half in range(max_num, max_num // 10, -1):
9 # Create the palindrome by reflecting the first half to create the second half.
10 second_half = reversed_half = first_half
11 palindrome = first_half
12 while reversed_half:
13 palindrome = palindrome * 10 + reversed_half % 10 # Append reversed digit.
14 reversed_half //= 10 # Remove last digit from reversed_half.
15
16 factor = max_num
17 # Check if the palindrome can be divided exactly by a number in the range.
18 while factor * factor >= palindrome:
19 if palindrome % factor == 0:
20 # If so, return the palindrome modulo 1337 as per problem constraints.
21 return palindrome % 1337
22 factor -= 1 # Reduce the factor and keep checking.
23
24 # If no palindrome product of two n-digit numbers is found, return 9
25 # This is the largest single-digit palindrome and is a special case for n = 1.
26 return 9
27
1class Solution {
2
3 // This method finds the largest palindrome that is a product of two n-digit numbers
4 public int largestPalindrome(int n) {
5
6 // The largest possible n-digit number
7 int maxDigitValue = (int) Math.pow(10, n) - 1;
8
9 // Looping from the largest n-digit number down to the smallest n-digit number
10 for (int firstFactor = maxDigitValue; firstFactor > maxDigitValue / 10; --firstFactor) {
11
12 // The second factor starts off identical to the first factor
13 int secondHalf = firstFactor;
14
15 // Beginning to construct the palindrome by considering the first factor
16 long possiblePalindrome = firstFactor;
17
18 // Mirroring the digits of the first factor to compose the second half of the palindrome
19 while (secondHalf != 0) {
20 possiblePalindrome = possiblePalindrome * 10 + secondHalf % 10;
21 secondHalf /= 10;
22 }
23
24 // Trying to find if the constructed palindrome has factors with n digits
25 for (long potentialFactor = maxDigitValue; potentialFactor * potentialFactor >= possiblePalindrome; --potentialFactor) {
26
27 // If the possiblePalindrome is divisible by potentialFactor, it is a palindrome that is a product of two n-digit numbers
28 if (possiblePalindrome % potentialFactor == 0) {
29
30 // Return the palindrome modulo 1337 as per the problem's requirement
31 return (int) (possiblePalindrome % 1337);
32 }
33 }
34 }
35
36 // If no palindrome can be found that is a product of two n-digit numbers, return 9
37 // This happens in the case where n = 1
38 return 9;
39 }
40}
41
1class Solution {
2public:
3 int largestPalindrome(int n) {
4 // Calculate the maximum number based on the digit count n
5 int maxNumber = pow(10, n) - 1;
6
7 // Start from the maximum number and iterate downwards
8 for (int number = maxNumber; number > maxNumber / 10; --number) {
9 long palindrome = number; // This will be used to form the palindrome
10 int reverse = number; // We will reverse "number" to create the palindrome
11
12 // Create the palindrome by appending the reverse of "number" to itself
13 while (reverse) {
14 palindrome = palindrome * 10 + reverse % 10; // Add the last digit of reverse to palindrome
15 reverse /= 10; // Remove the last digit from reverse
16 }
17
18 // Start from the maximum number and try to find a divisor
19 for (long testDivisor = maxNumber; testDivisor * testDivisor >= palindrome; --testDivisor) {
20 // Check if palindrome is divisible by testDivisor
21 if (palindrome % testDivisor == 0) {
22 // Return the palindrome modulo 1337
23 return palindrome % 1337;
24 }
25 }
26 }
27
28 // This is a special case for one-digit palindromes,
29 // which is the largest palindrome with one digit (9)
30 // since the loop iterations start for n > 1.
31 return 9;
32 }
33};
34
1function largestPalindrome(n: number): number {
2 // Calculate the maximum number based on the digit count n
3 const maxNumber: number = Math.pow(10, n) - 1;
4
5 // Start from the maximum number and iterate downwards
6 for (let number = maxNumber; number > maxNumber / 10; number--) {
7 let palindrome: number = number; // The current half of the palindrome
8 let reverse: number = number; // Will reverse the number to create the palindrome
9
10 // Create the palindrome by appending the reverse of "number" to itself
11 while (reverse > 0) {
12 palindrome = palindrome * 10 + reverse % 10; // Add the last digit of reverse to the palindrome
13 reverse = Math.floor(reverse / 10); // Remove the last digit from reverse
14 }
15
16 // Try to find a divisor starting from the maximum number
17 for (let testDivisor = maxNumber; testDivisor * testDivisor >= palindrome; testDivisor--) {
18 // Check if palindrome is divisible by testDivisor
19 if (palindrome % testDivisor === 0) {
20 // Return the palindrome modulo 1337
21 return palindrome % 1337;
22 }
23 }
24 }
25
26 // This is a special case for one-digit palindromes,
27 // which is the largest palindrome with one digit (9)
28 // since the loop iterations start for n > 1.
29 return 9;
30}
31
Time and Space Complexity
The given Python code is designed to find the largest palindromic number that can be produced from the product of two n
-digit numbers.
Time Complexity:
The time complexity of the code is determined by the nested loops and the operations within those loops.
-
The first loop runs for approximately
mx / 10
times, which is10^n / 10 = 10^(n-1)
iterations, as it starts frommx
and decrements until it reachesmx / 10
. This gives us the loop running inO(10^(n-1))
. -
Inside the first loop, we create a palindromic number
x
based on the current value ofa
. The innerwhile
loop used to createx
iterates once for each digit ina
, which isn
times. Therefore, the palindromic number creation runs inO(n)
time. -
The second while loop iterates at most
t
times, wheret
starts atmx
and is decremented untilt * t >= x
. Sincex
can be as large asmx^2
, and we are decrementingt
one by one, the upper bound for the number of iterations ismx
, leading to a worst-case time complexity ofO(mx)
for this loop, which isO(10^n)
. -
The nested loops result in a combined time complexity of
O(10^(n-1) * n * 10^n) = O(n * 10^(2n-1))
.
The time complexity is exponential, primarily due to the two nested loops where the outer loop is proportional to 10^(n-1)
and the inner loop could potentially iterate up to 10^n
.
Space Complexity:
The space complexity of the code is determined by the variables used and any additional space allocated during the execution of the algorithm.
-
Variables
a
,b
,x
,t
, andmx
use a constant amount of space. -
The creation of the palindromic number does not use any additional data structures that grow with the input size.
Therefore, the space complexity of the code is O(1)
, indicating constant space usage regardless of the input size n
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following array represent a max heap?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.