[C#][LeetCode] 479. Largest Palindrome Product

題目

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].

解題過程

這題要找出 N 位數相乘後且結果是迴文的數字
例如:N = 2 最大數字等於 99,那就要找出最大 99 最小 10 的兩位數相乘後且結果是迴文的數字。

最初我用一個很笨的方法迴圈慢慢跑,最後當然是直接逾時,後來改成先取最大數字相乘後的前半段數字,再用迴圈去產生迴文並篩選資料,這樣比前面的笨方法快非常多。

答案

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public int Solution2(int n)
{
if (n == 1)
{
return 9;
}

int maxBound = (int)Math.Pow(10, n) - 1;
int minBound = (int)Math.Pow(10, n - 1);
long maxNum = (long)maxBound * (long)maxBound;

string str = maxNum.ToString();
long maxFront = long.Parse(str.Substring(0, str.Length / 2));

for (long i = maxFront; i > 0; i--)
{
long palindrome = long.Parse(i.ToString() + Reverse(i.ToString()));

for (long j = maxBound; j > minBound; j--)
{
// 避免超出 N 位數
if (palindrome / j > maxBound)
{
break;
}

if (palindrome % j == 0)
{
return (int)(palindrome % 1337);
}
}
}

return 0;
}

public string Reverse(string s)
{
char[] charArray = s.ToCharArray();
Array.Reverse(charArray);
return new string(charArray);
}