Skip to content

479. Largest Palindrome Product 👎

  • Time: $O(10^n)$
  • Space: $O(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
25
26
27
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);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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