題目

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 的兩位數相乘後且結果是迴文的數字。

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

答案

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