479. Largest Palindrome Product LeetCode Solution

In this guide, you will get 479. Largest Palindrome Product LeetCode Solution with the best time and space complexity. The solution to Largest Palindrome Product problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Largest Palindrome Product solution in C++
4. Largest Palindrome Product solution in Java
5. Largest Palindrome Product solution in Python
6. Additional Resources

Problem Statement of Largest Palindrome Product

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

Complexity Analysis

• Time Complexity: O(10^n)
• Space Complexity: O(1)

479. Largest Palindrome Product LeetCode Solution in C++

class Solution {
 public:
  int largestPalindrome(int n) {
    if (n == 1)
      return 9;

    constexpr int kMod = 1337;
    const int upper = pow(10, n) - 1;
    const int lower = pow(10, n - 1) - 1;

    for (int i = upper; i > lower; --i) {
      const long cand = getPalindromeCandidate(i);
      for (long j = upper; j * j >= cand; --j)
        if (cand % j == 0)
          return cand % kMod;
    }

    throw;
  }

 private:
  long getPalindromeCandidate(int i) {
    string reversed = to_string(i);
    ranges::reverse(reversed);
    return stol(to_string(i) + reversed);
  }
};
/* code provided by PROGIEZ */

479. Largest Palindrome Product LeetCode Solution in Java

class Solution {
  public int largestPalindrome(int n) {
    if (n == 1)
      return 9;

    final int kMod = 1337;
    final int upper = (int) Math.pow(10, n) - 1;
    final int lower = (int) Math.pow(10, n - 1) - 1;

    for (int i = upper; i > lower; --i) {
      final long cand = getPalindromeCandidate(i);
      for (long j = upper; j * j >= cand; --j)
        if (cand % j == 0)
          return (int) (cand % kMod);
    }

    throw new IllegalArgumentException();
  }

  private long getPalindromeCandidate(int i) {
    final String reversed = new StringBuilder().append(i).reverse().toString();
    return Long.valueOf(i + reversed);
  }
}
// code provided by PROGIEZ

479. Largest Palindrome Product LeetCode Solution in Python

class Solution:
  def largestPalindrome(self, n: int) -> int:
    if n == 1:
      return 9

    kMod = 1337
    upper = pow(10, n) - 1
    lower = pow(10, n - 1) - 1

    for i in range(upper, lower, -1):
      cand = int(str(i) + str(i)[::-1])
      j = upper
      while j * j >= cand:
        if cand % j == 0:
          return cand % kMod
        j -= 1
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.