Largest Palindrome Product - Practice Coding Problems

Largest Palindrome Product - Problem

Math Enumeration Hard

Given an integer n, return the largest palindromic integer that can be represented as the product of two n-digit integers.

Since the result can be very large, return it modulo 1337.

For example, if n = 2, we need to find the largest palindrome that is the product of two 2-digit numbers (from 10 to 99). The largest palindrome would be 9009 = 91 × 99.

Note: For n = 1, the answer is 9 since 3 × 3 = 9 is the largest palindromic product of two 1-digit numbers.

Input & Output

Example 1 — Basic Case

$ Input: n = 2

› Output: 906

💡 Note: We need the largest palindrome from products of 2-digit numbers (10-99). The largest is 9009 = 91 × 99. Return 9009 % 1337 = 906.

Example 2 — Single Digit

$ Input: n = 1

› Output: 9

💡 Note: For 1-digit numbers (1-9), the largest palindromic product is 3 × 3 = 9. Since 9 < 1337, we return 9.

Example 3 — Larger Case

$ Input: n = 3

› Output: 123

💡 Note: For 3-digit numbers (100-999), we find the largest palindromic product and return it modulo 1337. The actual palindrome is much larger than 1337.

Constraints

1 ≤ n ≤ 8

Visualization

Tap to expand

Understanding the Visualization

Input

Given n=2, we work with 2-digit numbers (10 to 99)

Process

Find products that form palindromes: 91×99=9009

Output

Return largest palindrome modulo 1337: 906

Key Takeaway

🎯 Key Insight: Generate palindromes from largest to smallest instead of checking all products

Asked in

G Google 12 f Facebook 8 M Microsoft 6

The key insight is to generate palindromes in descending order rather than checking all products. For each palindrome, we verify if it can be factored into two n-digit numbers. The optimized approach uses palindrome generation with factorization checking. Time: O(10^n × √P), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Palindrome Generation Approach	O(10^n × √P)	O(1)	Generate palindromes from largest to smallest and check if they can be factored by two n-digit numbers
Brute Force - Check All Products	O(10^(2n))	O(1)	Try all pairs of n-digit numbers and find the largest palindromic product

Palindrome Generation Approach — Algorithm Steps

Generate palindromes from largest possible down to smallest
For each palindrome, try to find two n-digit factors
Use optimization: if i² < palindrome, no valid factorization exists
Return first valid palindrome found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Palindromes

Create palindromes from largest to smallest systematically

Check Factors

For each palindrome, verify if it has two n-digit factors

First Valid

Return the first palindrome that can be factored

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int canBeFactored(long long palindrome, long long lower, long long upper) {
    for (long long i = upper; i >= lower; i--) {
        if (i * i < palindrome) break;
        if (palindrome % i == 0) {
            long long factor = palindrome / i;
            if (factor >= lower && factor <= upper) {
                return 1;
            }
        }
    }
    return 0;
}

void reverseString(char* str) {
    int len = strlen(str);
    for (int i = 0; i < len/2; i++) {
        char temp = str[i];
        str[i] = str[len-1-i];
        str[len-1-i] = temp;
    }
}

int solution(int n) {
    if (n == 1) return 9;
    
    long long lower = (long long)pow(10, n-1);
    long long upper = (long long)pow(10, n) - 1;
    
    char maxStr[50];
    sprintf(maxStr, "%lld", upper * upper);
    int maxLen = strlen(maxStr);
    
    for (int length = maxLen; length > 0; length--) {
        if (length % 2 == 0) {
            int halfLen = length / 2;
            long long start = (long long)pow(10, halfLen-1);
            long long end = (long long)pow(10, halfLen) - 1;
            
            for (long long i = end; i >= start; i--) {
                char leftHalf[25];
                sprintf(leftHalf, "%lld", i);
                char rightHalf[25];
                strcpy(rightHalf, leftHalf);
                reverseString(rightHalf);
                
                char palindromeStr[50];
                sprintf(palindromeStr, "%s%s", leftHalf, rightHalf);
                long long palindrome = atoll(palindromeStr);
                
                if (canBeFactored(palindrome, lower, upper)) {
                    return palindrome % 1337;
                }
            }
        }
    }
    return 0;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", solution(n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(10^n × √P)

Generate O(10^n) palindromes, for each check O(√P) possible factors where P is palindrome value

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for computations

✓ Linear Space

12.5K Views

Medium Frequency

~35 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Palindrome Generation Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler