Scale Engineer

Largest Palindrome Product

Hard
#0466Time: 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.
Patterns
MathEnumeration

Prompt

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

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 - 1 and the lower bound is 10^(n-1).
  • Initialize a variable maxPalindrome to 0 to store the largest palindrome found.
  • Use a nested loop to iterate through all pairs of n-digit numbers. The outer loop for i runs from upper down to lower.
  • The inner loop for j runs from i down to lower to avoid duplicate products (i*j and j*i).
  • Inside the inner loop, calculate the product p = i * j.
  • As an optimization, if p is already smaller than maxPalindrome, we can break the inner loop because subsequent products for the current i will be even smaller.
  • Check if p is a palindrome. This can be done by converting the number to a string and checking if it reads the same forwards and backward.
  • If p is a palindrome, update maxPalindrome = 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.

Solutions

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;  }}

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.

← Previous

Previous problem

Next →

Next problem