資訊專欄INFORMATION COLUMN
Problem
Find the largest palindrome made from the product of two n-digit numbers.
Since the result could be very large, you should return the largest palindrome mod 1337.
ExampleInput: 2
Output: 987
Explanation: 99 x 91 = 9009, 9009 % 1337 = 987
public class Solution {
/**
* @param n: the number of digit
* @return: the largest palindrome mod 1337
*/
public int largestPalindrome(int n) {
// when n == 1, largest palindrome would be single-digit
if (n == 1) return 9;
// get the maximum and the minimum factors
long maxFactor = (long)Math.pow(10, n)-1;
long minFactor = (long)Math.pow(10, n-1);
// get the largest product first, then use the first half to create palindrome
long maxProduct = (long)maxFactor * (long)maxFactor;
long maxHalf = maxProduct / (long)Math.pow(10, n);
// initialize result palindrome to 0, and set the flag to check if result found and end the while loop
long palindrome = 0;
boolean palindromeFound = false;
while (!palindromeFound) {
// generate the latest largest palindrome in each cycle
palindrome = generatePalindrome(maxHalf);
for (long i = maxFactor; i >= minFactor; i--) {
// the generated palindrome cannot be larger than maxFactor * maxFactor
if (palindrome / i > i || palindrome / maxFactor > maxFactor) {
break;
}
if (palindrome % i == 0) {
palindromeFound = true;
break;
}
}
//when for loop ends, decrease maxHalf by 1 to generate the next palindrome
maxHalf--;
}
return (int)(palindrome % 1337);
}
public long generatePalindrome(long num) {
String str = String.valueOf(num) + new StringBuilder().append(num).reverse().toString();
return Long.parseLong(str);
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/69717.html
Valid Palindrome Problem Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. Example A man, a plan, a canal: Panama is a palindrome. race a ca...
#1. Reverse a String Reverse the provided string. You may need to turn the string into an array before you can reverse it. Your result must be a string. function reverseString(str/*:string*/) { if ...
摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...
摘要：自己沒事刷的一些的題目，若有更好的解法，希望能夠一起探討項(xiàng)目地址 自己沒事刷的一些LeetCode的題目，若有更好的解法，希望能夠一起探討 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...
摘要：復(fù)雜度思路要保留一個(gè)到某一位來看的最大值和最小值。因?yàn)樵跀?shù)組中有負(fù)數(shù)的出現(xiàn)，所以到這一位為止的能得到的最大值，可能是由之前的最大值和這個(gè)數(shù)相乘得到，也可能是最小值和這個(gè)數(shù)相乘得到的。 Leetcode[152] Maximum Product Subarray Find the contiguous subarray within an array (containing at le...
閱讀 1343·2021-11-15 11:37
閱讀 2607·2021-09-22 10:56
閱讀 3427·2021-09-06 15:11
閱讀 833·2021-08-31 09:45
閱讀 2950·2021-07-28 11:16
閱讀 1833·2019-08-30 15:44
閱讀 508·2019-08-30 13:22
閱讀 3371·2019-08-30 13:18
