Jobs

Interviews

Discussions

Largest Palindrome Product

Hard

Asked by:

8 views

Topics:

Greedy AlgorithmsMath

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

Try coding it in LeetCode

Largest Palindrome Product

Hard

Asked by:

8 views

Topics:

Greedy AlgorithmsMath

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the valid range for the input n? Can n be less than 1?
If no palindrome can be formed from the product of two n-digit numbers, what should I return?
Can you provide a specific example of the expected output for n = 2?
When you say "largest palindrome", are you referring to the numerical value of the palindrome, or something else?
Are we guaranteed that the product of two n-digit numbers will fit within the standard integer limits or should I consider using long data type?

Brute Force Solution

Approach

The problem asks us to find the biggest palindrome that can be made by multiplying two numbers with a specific number of digits. The brute force way to do this is to just try every possible multiplication and see if the result is both a palindrome and the biggest one we've found so far.

Here's how the algorithm would work step-by-step:

First, figure out the range of numbers to check. For example, if we're looking for the product of two 2-digit numbers, we need to check all numbers from 10 to 99.
Then, multiply every number in that range by every other number in that range. This means a lot of multiplications!
For each product, check if it's a palindrome. A palindrome reads the same forwards and backward.
If the product is a palindrome, compare it to the largest palindrome we've found so far.
If the current palindrome is bigger, replace the largest palindrome we've found with the current one.
After checking all possible products, the largest palindrome we've found is the answer.

Code Implementation

def largest_palindrome_product_brute_force(number_of_digits):
    minimum_number = 10 ** (number_of_digits - 1)
    maximum_number = (10 ** number_of_digits) - 1

    largest_palindrome = 0

    # Iterate through all possible combinations
    for first_number in range(minimum_number, maximum_number + 1):
        for second_number in range(minimum_number, maximum_number + 1):
            product = first_number * second_number

            # Convert product to string for palindrome check
            product_string = str(product)

            # Check if the product is a palindrome
            if product_string == product_string[::-1]:

                #Update largest palindrome if needed
                if product > largest_palindrome:
                    largest_palindrome = product

    return largest_palindrome

Big(O) Analysis

Time Complexity

O(10^(2n)) – The algorithm iterates through all possible products of two n-digit numbers. The range of n-digit numbers is approximately from 10^(n-1) to 10^n - 1. Therefore, we have two nested loops, each iterating roughly 10^n times. The palindrome check within the inner loop takes O(number of digits), which is O(2n), a linear time. The dominant factor comes from the nested loops, leading to approximately (10^n) * (10^n) or 10^(2n) operations. Therefore, the overall time complexity is O(10^(2n)).

Space Complexity

O(1) – The provided brute force algorithm iterates through a range of numbers and calculates their products. It only needs to store a few variables like the current product, the largest palindrome found so far, and loop counters. The space required for these variables remains constant irrespective of the number of digits (N) given as input. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The key is to search for palindrome products in a decreasing order. Since we want the largest palindrome product made from two n-digit numbers, we generate palindromes that could be products of n-digit numbers, testing the largest ones first. This lets us quit early once we've found a suitable palindrome.

Here's how the algorithm would work step-by-step:

Start by creating the largest possible palindrome that can be formed by multiplying two n-digit numbers. Build it by combining the largest possible n-digit number with its reverse.
Check if the created palindrome can be divided evenly by any n-digit number. If it can, check if the resulting quotient is also an n-digit number.
If both the divisor and quotient are n-digit numbers, then we've found our answer, the largest palindrome product.
If not, generate the next largest palindrome by reducing the first half of the palindrome by one, and then combining with its reverse.
Repeat the process of checking for n-digit divisors and quotients until a valid pair of n-digit numbers is found or until we've reached the smallest possible palindrome.
The first palindrome found that results from the multiplication of two n-digit numbers is our answer; we can stop searching once this is found because it will be the largest one.

Code Implementation

def largest_palindrome_product(number_of_digits):
    max_number = 10**number_of_digits - 1
    min_number = 10**(number_of_digits - 1)

    largest_palindrome = 0

    for i in range(max_number, min_number - 1, -1):
        # Construct the palindrome by combining 'i' with its reverse.
        palindrome = int(str(i) + str(i)[::-1])

        # Iterate downwards to find factors
        for j in range(max_number, min_number - 1, -1):
            if palindrome % j == 0:
                factor2 = palindrome // j

                # Verify both factors are within the specified digit range
                if min_number <= factor2 <= max_number:
                    largest_palindrome = palindrome
                    return largest_palindrome

    return largest_palindrome

Big(O) Analysis

Time Complexity

O(10^n) – The algorithm iterates through potential palindromes in decreasing order, derived from the largest possible n-digit number. The number of potential palindromes to check grows exponentially with n, specifically, in the order of 10^n because the largest n-digit number is close to 10^n. For each palindrome, it checks for divisibility by numbers also in the range of n-digit numbers. Therefore, the overall complexity is dominated by the number of palindromes generated and the divisibility checks performed on each, leading to a time complexity of approximately O(10^n).

Space Complexity

O(1) – The algorithm primarily uses variables to store the current palindrome being tested and potential divisors. Since the size of these variables does not depend on the input 'n' (number of digits), but remains constant, the auxiliary space used is constant. The algorithm generates palindromes and checks divisibility without using any dynamically sized data structures that would scale with the input. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
n = 1: The largest palindrome from the product of two 1-digit numbers.	Handle the base case n=1 separately returning 9 since 9 * 9 = 81 and 8 is the largest palindrome.
n > 7: Potential integer overflow when multiplying n-digit numbers.	Use a data type that can store large numbers (e.g., long in Java/C++, Python's automatic large integer support) and apply the modulo operator (%) during intermediate calculations to prevent overflow, ensuring calculations are done within modulo range.
No palindrome exists for a given n.	The algorithm should iterate through potential palindrome candidates in descending order; if it exhausts all possibilities without finding a valid factor pair, return 0, indicating no solution exists.
Input n is zero or negative.	Return 0 if n is zero or negative, indicating invalid input, as the problem statement defines n as the number of digits.
Finding factors for very large palindromes	Optimize the factorization process by iterating down from the largest possible n-digit number; this way, we can quickly find the largest factor and avoid unnecessary computations.
The largest n-digit number squared is not a palindrome.	The algorithm needs to correctly handle cases where the product of the two largest n-digit numbers does not produce a palindrome, by continuing to search for smaller palindromes.
Palindrome generation logic error	Double-check the palindrome generation logic (creating a palindrome from half of the number), ensuring it handles both even and odd length palindromes correctly.
Time limit exceeded for larger values of n	Optimize by using appropriate bounds on the search space for factors and early stopping conditions to improve efficiency.

n = 1: The largest palindrome from the product of two 1-digit numbers.

How to Handle:

Handle the base case n=1 separately returning 9 since 9 * 9 = 81 and 8 is the largest palindrome.

n > 7: Potential integer overflow when multiplying n-digit numbers.

How to Handle:

Use a data type that can store large numbers (e.g., long in Java/C++, Python's automatic large integer support) and apply the modulo operator (%) during intermediate calculations to prevent overflow, ensuring calculations are done within modulo range.

No palindrome exists for a given n.

How to Handle:

The algorithm should iterate through potential palindrome candidates in descending order; if it exhausts all possibilities without finding a valid factor pair, return 0, indicating no solution exists.

Input n is zero or negative.

How to Handle:

Return 0 if n is zero or negative, indicating invalid input, as the problem statement defines n as the number of digits.

Finding factors for very large palindromes

How to Handle:

Optimize the factorization process by iterating down from the largest possible n-digit number; this way, we can quickly find the largest factor and avoid unnecessary computations.

The largest n-digit number squared is not a palindrome.

How to Handle:

The algorithm needs to correctly handle cases where the product of the two largest n-digit numbers does not produce a palindrome, by continuing to search for smaller palindromes.

Palindrome generation logic error

How to Handle:

Double-check the palindrome generation logic (creating a palindrome from half of the number), ensuring it handles both even and odd length palindromes correctly.

Time limit exceeded for larger values of n

How to Handle:

Optimize by using appropriate bounds on the search space for factors and early stopping conditions to improve efficiency.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the valid range for the input n? Can n be less than 1?
If no palindrome can be formed from the product of two n-digit numbers, what should I return?
Can you provide a specific example of the expected output for n = 2?
When you say "largest palindrome", are you referring to the numerical value of the palindrome, or something else?
Are we guaranteed that the product of two n-digit numbers will fit within the standard integer limits or should I consider using long data type?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, figure out the range of numbers to check. For example, if we're looking for the product of two 2-digit numbers, we need to check all numbers from 10 to 99.
Then, multiply every number in that range by every other number in that range. This means a lot of multiplications!
For each product, check if it's a palindrome. A palindrome reads the same forwards and backward.
If the product is a palindrome, compare it to the largest palindrome we've found so far.
If the current palindrome is bigger, replace the largest palindrome we've found with the current one.
After checking all possible products, the largest palindrome we've found is the answer.

Code Implementation

def largest_palindrome_product_brute_force(number_of_digits):
    minimum_number = 10 ** (number_of_digits - 1)
    maximum_number = (10 ** number_of_digits) - 1

    largest_palindrome = 0

    # Iterate through all possible combinations
    for first_number in range(minimum_number, maximum_number + 1):
        for second_number in range(minimum_number, maximum_number + 1):
            product = first_number * second_number

            # Convert product to string for palindrome check
            product_string = str(product)

            # Check if the product is a palindrome
            if product_string == product_string[::-1]:

                #Update largest palindrome if needed
                if product > largest_palindrome:
                    largest_palindrome = product

    return largest_palindrome

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by creating the largest possible palindrome that can be formed by multiplying two n-digit numbers. Build it by combining the largest possible n-digit number with its reverse.
Check if the created palindrome can be divided evenly by any n-digit number. If it can, check if the resulting quotient is also an n-digit number.
If both the divisor and quotient are n-digit numbers, then we've found our answer, the largest palindrome product.
If not, generate the next largest palindrome by reducing the first half of the palindrome by one, and then combining with its reverse.
Repeat the process of checking for n-digit divisors and quotients until a valid pair of n-digit numbers is found or until we've reached the smallest possible palindrome.
The first palindrome found that results from the multiplication of two n-digit numbers is our answer; we can stop searching once this is found because it will be the largest one.

Code Implementation

def largest_palindrome_product(number_of_digits):
    max_number = 10**number_of_digits - 1
    min_number = 10**(number_of_digits - 1)

    largest_palindrome = 0

    for i in range(max_number, min_number - 1, -1):
        # Construct the palindrome by combining 'i' with its reverse.
        palindrome = int(str(i) + str(i)[::-1])

        # Iterate downwards to find factors
        for j in range(max_number, min_number - 1, -1):
            if palindrome % j == 0:
                factor2 = palindrome // j

                # Verify both factors are within the specified digit range
                if min_number <= factor2 <= max_number:
                    largest_palindrome = palindrome
                    return largest_palindrome

    return largest_palindrome

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n = 1: The largest palindrome from the product of two 1-digit numbers.	Handle the base case n=1 separately returning 9 since 9 * 9 = 81 and 8 is the largest palindrome.
n > 7: Potential integer overflow when multiplying n-digit numbers.	Use a data type that can store large numbers (e.g., long in Java/C++, Python's automatic large integer support) and apply the modulo operator (%) during intermediate calculations to prevent overflow, ensuring calculations are done within modulo range.
No palindrome exists for a given n.	The algorithm should iterate through potential palindrome candidates in descending order; if it exhausts all possibilities without finding a valid factor pair, return 0, indicating no solution exists.
Input n is zero or negative.	Return 0 if n is zero or negative, indicating invalid input, as the problem statement defines n as the number of digits.
Finding factors for very large palindromes	Optimize the factorization process by iterating down from the largest possible n-digit number; this way, we can quickly find the largest factor and avoid unnecessary computations.
The largest n-digit number squared is not a palindrome.	The algorithm needs to correctly handle cases where the product of the two largest n-digit numbers does not produce a palindrome, by continuing to search for smaller palindromes.
Palindrome generation logic error	Double-check the palindrome generation logic (creating a palindrome from half of the number), ensuring it handles both even and odd length palindromes correctly.
Time limit exceeded for larger values of n	Optimize by using appropriate bounds on the search space for factors and early stopping conditions to improve efficiency.

n = 1: The largest palindrome from the product of two 1-digit numbers.

How to Handle:

Handle the base case n=1 separately returning 9 since 9 * 9 = 81 and 8 is the largest palindrome.

n > 7: Potential integer overflow when multiplying n-digit numbers.

How to Handle:

No palindrome exists for a given n.

How to Handle:

Input n is zero or negative.

How to Handle:

Return 0 if n is zero or negative, indicating invalid input, as the problem statement defines n as the number of digits.

Finding factors for very large palindromes

How to Handle:

Optimize the factorization process by iterating down from the largest possible n-digit number; this way, we can quickly find the largest factor and avoid unnecessary computations.

The largest n-digit number squared is not a palindrome.

How to Handle:

The algorithm needs to correctly handle cases where the product of the two largest n-digit numbers does not produce a palindrome, by continuing to search for smaller palindromes.

Palindrome generation logic error

How to Handle:

Double-check the palindrome generation logic (creating a palindrome from half of the number), ensuring it handles both even and odd length palindromes correctly.

Time limit exceeded for larger values of n

How to Handle:

Optimize by using appropriate bounds on the search space for factors and early stopping conditions to improve efficiency.