Project Euler 4: Largest palindrome product

This solves Project Euler 4: Largest palindrome product using C# (specifically, using LINQPad). Any and all suggestions for improvements to either the C# code or the math/algorithm are very welcome.


A palindromic number reads the same both ways. The largest palindrome
made from the product of two 2-digit numbers is 9009 = 91 × 99.


Find the largest palindrome made from the product of two 3-digit
numbers.

The code finds the answer to the 2-digit test case in about 3ms, and the 3-digit test case in about 250ms. The additional 4-digit test takes about 27 seconds so it is kind of slow.

I tried to find a mathematical solution to palindromes, but since the problem is lexical in nature, I had to resort to string manipulation. I wrote an extension method or two that I used in this problem...

IntUtils

public static class IntUtils
{ 
    // Equivalent to Math.Pow(long) for int type.
    public static int Pow(int baseNum, int exponent)
    {
        if (exponent == 0) { return 1; }
        else if (exponent == 1) { return baseNum; }
        else 
        {
            while (exponent > 1)
            {
                baseNum *= baseNum;
                exponent--;
            }
        }
        return baseNum;
    }
    // Check if a number is palindrome, i.e., reads the same backward or forward.
    public static bool IsPalindrome(int number)
    {
        string lexicalNumber = number.ToString();
        return lexicalNumber.Equals(StringUtils.Reverse(lexicalNumber));    
}

StringUtils

public class StringUtils
{
    public static string Reverse(string s)
    {
        // Source: http://stackoverflow.com/a/228060/3626537
        char[] chars = s.ToCharArray();
        Array.Reverse(chars);
        return new string(chars);
    }
}

The solution code:

```
// ProjectEuler4: Largest palindrome product
// https://projecteuler.net/problem=4
void Main()
{
Console.WriteLine("ProjectEuler4: Largest palindrome product");
// this is the t

CurrentCode

Ascertaining whether or not a number is a palindrome seems slow. The code

• Converts from number to string

• Reverses the string

• Creates a new string

• Compares the two strings

Once the we have converted the number to a string we can just use an Is the string a Palindrome routine to check. In some quick tests it took about 2/3 of the time.

private static bool IsPalindrome(int number)
{
    string lexicalNumber = number.ToString();
    int start = 0;
    int end = lexicalNumber.Length-1;
    while(start < end)
    {
        if(lexicalNumber[start++] != lexicalNumber[end--])
        {
            return false;
        }
    }
    return true;
}

IntUtils.Pow seems like overkill.

for (int minNum = (minAndMax[0] * minAndMax[0]), maxNum = (minAndMax[1] * minAndMax[1]); minNum <= maxNum; minNum++)

does the same job with a lot less clutter.

We wish to examine the palindromes in descending order and stop when we reach the first with valid factors. By returning the values in a List we are checking all the numbers in the range and adding them to the list before we do the first test. This is where yield comes in:

private static IEnumerable GetPalindromes(int min, int max)
{
    for(var value = (max * max); value >=(min*min); value--)
    {
        if (IsPalindrome(value))
        {
            yield return value;
        }
    }
}

By using yield and by not having to reverse the list we get an order of magnitude (13 ms vs 150 ms in my tests) improvement in time. The processing is now

FOR EACH NUMBER IN THE RANGE (DESCENDING)

- Check to see if the number is a palindrome

- Check to set if it has valid factors

- Stop if success

END

rather than

FOR EACH NUMBER IN THE RANGE (DESCENDING)

- Check to see if the number is a palindrome

END

FOR EACH NUMBER IN THE RANGE (DESCENDING)

- Check to set if has valid factors

- Stop if success

END

NOTE: Having to use Reverse() kills any benefits from yield as the whole Enumerable needs to be evaluated before we can start using it, so changing the generation order is very important.

Performance

With these changes I am getting the following timings

Found 9999, 9901 => 99000099 in 182 ms 
Found 993, 913 => 906609 in 13 ms

Approach

Instead of

• Testing all numbers in the allowed range to see if they are palindromes

• Finding the factors for each of these

We might approach it by generating the palindromes in each

e.g.

If we are trying the 3 digit version, we can generate the possible palindromes and test each

999 => 999999

998 => 998899

...

We can check the factors for each of these, starting at maxValue (999) and stopping at the square root of the plaindrome - because once we pass this point, we should have already found the pair of factors (We imply the square root by checking if factor2 > factor1 because I believe this to be faster but it may not be)

private static int[] FindPalindromeFactors(int min, int max)
{
    int lhs = max;
    while (lhs> 0)
    {
        var palindrome = BuildPalindrome(lhs--);
        for (int factor1 = max; factor1 >= min; factor1--)
        {

            var factor2 = palindrome / factor1;
            if (factor2 > max || (factor2 > factor1)  )
            {
                break;
            }

            if ((palindrome % factor1) == 0)
            {
                return new int []{ factor1, factor2 };
            }
        }
    }

    return null;
}

private static int BuildPalindrome(int lhs)
{
    var str = lhs.ToString(CultureInfo.InvariantCulture);
    return Convert.ToInt32(str + new string(str.Reverse().ToArray()));
}

Performance

With this approach I am getting the following timings

Found 993, 913 => 906609 in 2 ms
Found 9999, 9901 => 99000099 in 0 ms

Presumable, the 4 digit version is so fast because it only needs to check 100 possibilities 9999 -> 9000 and only needs to find the factors for these 100 numbers where

StackExchange Code Review Q#133345, answer score: 11