Project Euler - Problem 4 in C#

Largest palindrome product

Problem 4

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.

Sounds like pretty simple problem ... right.

For all the three digit numbers, find the product between them and check if the product of numbers is palindrome or not. And if yes, find the greatest product.

Like explained in the problem, a palindrome is a word, phrase, or number, whose meaning may be interpreted the same way in either forward or reverse direction. To test a palindrome number, we need to reverse the digits of the number. And for that, we iterate using formula ((y*10) + (x%10)) where y is new reversed number starting from 0 and x is original number to be reversed. Here is the example below to understand it better

Iteration	Formula	New Number (y)	Actual Number (x)
0	0	0	98743
1	(0*10) + (98743%10)	3	9874
2	(3*10) + (9874%10)	34	987
3	(34*10) + (987%10)	347	98
4	(347*10) + (98%10)	3478	9
5	(3478*10) + (9%10)	34789	0

Method to reverse digits and test if number is palindrome or not ....

// Check is number is palindrome
public static bool IsPalindrome(this int number)
{
    // store the actual number for check
    var actualNumber = number;
    // initialize new palindrome number
    var palindromeNumber = 0;

    // to reverse the number e.g. 98743 and set new palindrome number to 0
    // multiple new palindrome number with 10, and add modulus when number is divide by 10 and set it back in the new number
    // iteration 1 -> newPalindromeNumber: (0*10 + 98743%10) -> 3; number -> 9874
    // iteration 2 -> newPalindromeNumber: (3*10 + 9874%10) -> 34; number -> 987
    // iteration 3 -> newPalindromeNumber: (34*10 + 987%10) -> 347; number -> 98
    // iteration 4 -> newPalindromeNumber: (347*10 + 98%10) -> 3478; number -> 9
    // iteration 5 -> newPalindromeNumber: (3478*10 + 9%10) -> 34789; number -> 0
    // loops till number is not equal to 0
    // and now we have reversed number to check if its palindrome
    while (number != 0)
    {
        palindromeNumber = (palindromeNumber * 10) + (number % 10);
        number = number / 10;
    }
    //if actual number and new expected palindrome numbers are same
    return (actualNumber == palindromeNumber);
}

Here is the first basic implementation to solve the problem

// basic looping
public static IEnumerable<int> ListOfThreeDigitNumbersProduct()
{
    // looping for the first 3 digit numbers
    for (var i = 999; i > 99; i--)
    {
        // looping for the second 3 digit numbers
        for (var j = 999; j > 99; j--)
        {
            // find the product b/w the numbers
            var product = i*j;

            // check if the number is palindome
            if (product.IsPalindrome())
            {
                yield return product;
            }
        }
    }
}

Whats happening in this solution

• Number x and y iterate from 100 to 999 to find product of x with all the 3 digits y number.
• Every product is verified for palindrome test and if successful, added to the list of palindrome products of 3 digit number
• Max number is picked from the list of palindrome numbers from the list.

var maxProduct = ListOfThreeDigitNumbersProduct().Max();

Note: We don't need to create the list of palindrome numbers.We can put conditions to always compare and get the largest palindrome number.

This solution works but there is room for improvement .... :) . Here are my observation for improvement for faster solution ...

• Product of x*y is equal to y*x. So we don't need check the product of x with y and again for x = y and y = x. This can be avoided by setting upper bound y to x.
• If the new product is greater then the previously stored palindrome number, only then we should run palindrome test on the current number. This way we can avoid palindrome test processing time on many numbers, hence making solution faster.

// intelligent faster solution
public static int LargestThreeDigitNumbersProduct()
{
    // initialize largest palindrome number variabel
    var largestPalindromeNumber = 0; 

    // loopping thru all 3 digit numbers
    for (var i = 999; i > 99; i--)
    {
        // PERFORMACE BOOST
        // looping thru 3 digits number from 100 to first number
        // anything greater then first number has been already calculated
        // as (a*b) = (b*a)
        for (var j = 100; j <= i; j++)
        {
            // product of nunmbers
            var product = i*j;

            // PERFORMACE BOOST
            // if current product is greated then the previous saved palindrome product
            // only then check for number is palindrome else we can avoid extra checking task
            if (product > largestPalindromeNumber) 
            {
                // check number is palindrome
                if (product.IsPalindrome())
                {
                    // if is palindrome, save it as largest palindrome number 
                    largestPalindromeNumber = product;
                }
            }
        }
    }

    return largestPalindromeNumber;
}

Link to Problem #3

If you have a better solution, please don't hide it from us .... share your knowledge ... :) .... till then, enjoy solving problems.