In this Leetcode Largest Palindrome Product problem solution 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.
Problem solution in Python.
class Solution: def largestPalindrome(self, n: int) -> int: if n == 1: return 9 min_num = 10 ** (n - 1) max_num = 10 ** n - 1 max_pal = 0 for i in range(max_num, min_num - 1, -2): if i * i < max_pal: break for j in range(max_num, i - 1, -2): product = i * j if product % 11 != 0 and product >= max_pal: continue if str(product) == str(product)[::-1]: max_pal = product return max_pal % 1337
Problem solution in Java.
public int largestPalindrome(int n) { if (n == 1) return 9; int max = (int) Math.pow(10, n) - 1; int max_11 = (max / 11) * 11; long product; for (int i=max; i > (int) Math.pow(10, n-1); i--){ product = Long.parseLong(i + new StringBuilder(String.valueOf(i)).reverse().toString()); for (long j = max_11; j > (int) Math.pow(10, n-1); j-=11) { if ((product/j) / (max+1) == 0){ if (product%j==0) return (int)(product% 1337); } else break; } } return -1; }
Problem solution in C++.
class Solution {
public:
int largestPalindrome(int n) {
long max, min, ans = 0, sum;
max = static_cast<long>(pow(10, n)) - 1;
min = max/10 + 1;
sum = 2 * max;
while (sum/2 * (sum - sum/2) > ans){
long i = sum/2, j = sum - sum/2;
while (j <= max && i >= min){
long num = i * j;
if (num > ans && isPalindrome(num)){
ans = num;
break;
}
i--;
j++;
}
sum--;
}
return ans % 1337;
}
bool isPalindrome(long x){
long y = 0;
for (long z = x; z != 0; y = 10 * y + z % 10, z /= 10);
return x == y;
}
};
Problem solution in C.
long int creatPalindrome(long int num,int n){ long int p=num*pow(10,n); for(int i=0;i<n;i++){ p=p+(num/(long int)pow(10,n-i-1))*(long int)pow(10,i); num=num%(long int)pow(10,n-i-1); } return p; } int largestPalindrome(int n) { if(n==1){return 9;} long int p=pow(10,n)-1; long int q=p; long int temp=pow(10,n-1); long int ret=0; long int ret1=0; while(p>=temp){ ret=creatPalindrome(p,n); for(int i=q;i>=temp;i--){ ret1=ret/i; if(ret1>=i){break;} if(ret1>=temp&&ret%i==0){return ret%1337;} } p--; } return NULL; }
0 Comments