Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

479. Largest Palindrome Product

Time: $O(10^n)$

Space: $O(1)$

			


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);
    reverse(begin(reversed), end(reversed));
    return stol(to_string(i) + reversed);
  }
};




			


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




			


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