[LeetCode] 479. Largest Palindrome Product

轉自LeetCode

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.

Example:

Input: 2

Output: 987

Explanation: 99 x 91 = 9009, 9009 % 1337 = 987

Note:

The range of n is [1,8].

<Solution>

想法如下

• 因為要找最長的 palindrome，所以從兩個 n-digit 數字的最大乘積往下找

• 找到一個 palindrome 後，再去確認它是不是兩個 n-digit 數字的乘積

code 如下

C++

	class Solution {
	public:
	int largestPalindrome(int n) {
	if (n == 1) {
	return 9;
	}
	const int upperBound = static_cast<int>(pow(10.0, (double)n)) - 1;
	const int lowerBound = upperBound / 10;
	long palindrome;
	string numStr, reverseNumStr;
	for(int num = upperBound; num > lowerBound; num--) {
	numStr = to_string(num);
	reverseNumStr = to_string(num);
	reverse(reverseNumStr.begin(), reverseNumStr.end());
	palindrome = stol(numStr + reverseNumStr);
	//>> check the palindrome is the product of two n-digit number or not
	for(long p = upperBound; p*p >= palindrome; p--) {
	if(palindrome % p == 0) {
	return static_cast<int>(palindrome % 1337);
	}
	}
	}
	return 0;
	}
	};

view raw largestPalindromeProduct.cpp hosted with ❤ by GitHub

Java

	class Solution {
	public int largestPalindrome(int n) {
	if (n == 1) {
	return 9;
	}
	final int upperBound = (int) Math.pow(10, n) - 1;
	final int lowerBound = upperBound / 10;
	long palindrome;
	StringBuilder sb = new StringBuilder();
	for(int num = upperBound; num > lowerBound; num--) {
	sb.setLength(0); //>> reset
	palindrome = Long.valueOf(num + sb.append(num).reverse().toString());
	//>> check palindrome is a product of tow n-digit number or not
	for(long p = upperBound; p*p >= palindrome; p--) {
	if(palindrome % p == 0) {
	return (int)(palindrome % 1337);
	}
	}
	}
	return 0;
	}
	}

view raw largestPalindromeProduct.java hosted with ❤ by GitHub