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.

Examples

Example 1:

1
2
3
4
5

Input:
n = 2
Output:
 987
Explanation: 99 x 91 = 9009, 9009 % 1337 = 987

Example 2:

1
2
3
4

Input:
n = 1
Output:
 9

Solution

Method 1 – Construct Palindrome and Check Factorization

Intuition

The largest palindrome made from the product of two n-digit numbers must be close to the square of the largest n-digit number. Instead of checking all products, we can generate palindromes in descending order and check if they can be factored into two n-digit numbers.

Approach

  1. Start from the largest possible n-digit number and generate palindromes by mirroring the left half.
  2. For each palindrome, check if it can be written as a product of two n-digit numbers.
  3. If found, return the palindrome modulo 1337.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int largestPalindrome(int n) {
        if (n == 1) return 9;
        int upper = pow(10, n) - 1, lower = pow(10, n-1);
        for (long left = upper; left >= lower; --left) {
            string p = to_string(left);
            reverse(p.begin(), p.end());
            long pal = stol(to_string(left) + p);
            for (long x = upper; x * x >= pal; --x) {
                if (pal % x == 0) {
                    long y = pal / x;
                    if (y >= lower && y <= upper) return pal % 1337;
                }
            }
        }
        return -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func largestPalindrome(n int) int {
    if n == 1 {
        return 9
    }
    upper := int(math.Pow10(n)) - 1
    lower := int(math.Pow10(n - 1))
    for left := upper; left >= lower; left-- {
        s := strconv.Itoa(left)
        rev := ""
        for i := len(s) - 1; i >= 0; i-- {
            rev += string(s[i])
        }
        pal, _ := strconv.ParseInt(s+rev, 10, 64)
        for x := upper; int64(x)*int64(x) >= pal; x-- {
            if pal%int64(x) == 0 {
                y := pal / int64(x)
                if y >= int64(lower) && y <= int64(upper) {
                    return int(pal % 1337)
                }
            }
        }
    }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int largestPalindrome(int n) {
        if (n == 1) return 9;
        int upper = (int)Math.pow(10, n) - 1, lower = (int)Math.pow(10, n-1);
        for (long left = upper; left >= lower; --left) {
            StringBuilder sb = new StringBuilder();
            sb.append(left);
            sb.reverse();
            long pal = Long.parseLong(left + sb.toString());
            for (long x = upper; x * x >= pal; --x) {
                if (pal % x == 0) {
                    long y = pal / x;
                    if (y >= lower && y <= upper) return (int)(pal % 1337);
                }
            }
        }
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    fun largestPalindrome(n: Int): Int {
        if (n == 1) return 9
        val upper = Math.pow(10.0, n.toDouble()).toInt() - 1
        val lower = Math.pow(10.0, (n-1).toDouble()).toInt()
        for (left in upper downTo lower) {
            val s = left.toString()
            val pal = (s + s.reversed()).toLong()
            var x = upper
            while (x.toLong() * x >= pal) {
                if (pal % x == 0L) {
                    val y = pal / x
                    if (y >= lower && y <= upper) return (pal % 1337).toInt()
                }
                x--
            }
        }
        return -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def largestPalindrome(self, n: int) -> int:
        if n == 1:
            return 9
        upper = 10**n - 1
        lower = 10**(n-1)
        for left in range(upper, lower-1, -1):
            s = str(left)
            pal = int(s + s[::-1])
            for x in range(upper, int(pal**0.5)-1, -1):
                if pal % x == 0:
                    y = pal // x
                    if lower <= y <= upper:
                        return pal % 1337
        return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn largest_palindrome(n: i32) -> i32 {
        if n == 1 { return 9; }
        let upper = 10_i64.pow(n as u32) - 1;
        let lower = 10_i64.pow((n-1) as u32);
        for left in (lower..=upper).rev() {
            let s = left.to_string();
            let pal = format!("{}{}", s, s.chars().rev().collect::<String>()).parse::<i64>().unwrap();
            let mut x = upper;
            while x * x >= pal {
                if pal % x == 0 {
                    let y = pal / x;
                    if y >= lower && y <= upper {
                        return (pal % 1337) as i32;
                    }
                }
                x -= 1;
            }
        }
        -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    largestPalindrome(n: number): number {
        if (n === 1) return 9;
        const upper = Math.pow(10, n) - 1, lower = Math.pow(10, n-1);
        for (let left = upper; left >= lower; --left) {
            const s = left.toString();
            const pal = parseInt(s + s.split('').reverse().join(''));
            for (let x = upper; x * x >= pal; --x) {
                if (pal % x === 0) {
                    const y = pal / x;
                    if (y >= lower && y <= upper) return pal % 1337;
                }
            }
        }
        return -1;
    }
}

Complexity

  • ⏰ Time complexity: O(10^n * n), since we generate O(10^n) palindromes and for each, check up to O(10^n) factors, but in practice, it is much faster due to early breaks.
  • 🧺 Space complexity: O(1), only a constant amount of extra space is used.

Method 2 -

Code

Complexity

  • Time: O(nnnxxxnnn)
  • Space: O(nnnxxx)