Determining numeric palindromes

Question

I am working on bettering my C# skills, and recently wrote this program to solve a projecteuler.net problem:

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 works and produced the correct answer, but I'm looking to avoid bad code and use best practices. Any critique of changes to make this more efficient would be appreciated! (Also, if there are any WTF's in there, please point them out!)

using System;
using System.Collections.Generic;
using System.Text;

namespace NumericPalindrome {
    class Program
    {
        static void Main(string[] args)
        {
            long result = 0;

            for (int i = 100; i < 1000; i++)
            {
                for (int k = 100; k < 1000; k++)
                {
                    if (IsPalindrome(i * k))
                        if ((i * k) > result)
                            result = i * k;
                }
            }

            Console.WriteLine(result);
        }



        static bool IsPalindrome(long testNumber)
        {
            List<int> list = new List<int>();

            //Break testNumber into an integer list of its digits
            while (testNumber >= 1)
            {
                list.Add((int)(testNumber % 10));
                testNumber /= 10;
            }

            List<int> reverseList = new List<int>(list);
            reverseList.Reverse();

            bool palindrome = true;

            for (int i = 0; i < list.Count; i++)
            {
                if (list[i] != reverseList[i])
                    palindrome = false;
            }

            return palindrome;
        }
    }
}

Answer 1

• First of all, add benchmarking to your program: before anything else, record the current time. Right before the program terminates, subtract the recorded time from the current time and display the difference. Run it and record the time it takes. Then, implement the following optimizations, and see how much time you save.

• In your first nested two for-loops you are not taking advantage of the fact that AB = BA. So, you are doing about twice the work that is necessary. Cut it in half! (I presume that once you realize the idea, you can figure out how; if not, ask me.)

• The three repeated calculations of i * k are kind of ugly. Why don't you compute the product once, and use it 3 times? This is not a performance issue, just an aesthetic one.

• To check if the list is a palindrome, you do not need to make a copy of it and reverse. You can do something which far more efficient, and even easier to implement: loop from the start of the list until the middle, and compare the digit at that position with the corresponding digit counting from the end of the list. If the list contains an odd number of digits, ignore the one in the middle. (Again, I presume you can figure it out; if not, ask me.)

• You can return false from within the loop immediately upon finding that the number is not a palindrome; it is totally unnecessary to keep looping until you have checked all the digits.

• If you really-really care about performance, you can start doing hacks, like making the list a static member variable of your program, allocating once, and clearing it each time before using it, instead of reallocating a new list each time. You can also find an algorithm which can determine whether a number is a palindrome without constructing a list. It is ugly, but it works; look here: https://stackoverflow.com/questions/199184/how-do-i-check-if-a-number-is-a-palindrome

Answer 2

I do not do C# but I can offer another way of approaching the problem:

As our range of numbers is \$[100\cdot100, 999\cdot999] = [10000, 998001]\$, assume a palindromic number on the form \$abccba\$.

The largest \$abccba < 998001\$ is \$k = abccba = 997799\$. We need to determine if \$k\$ can be written as the product of two 3-digit numbers. Using a prime table (or generate one with a sieve at program start) see if any prime number \$p\$ where \$\min\left(\frac{k}{100}, 999\right) \lt p\le k\$ evenly divides \$k\$.

If you can find such a prime then we know that \$\frac{k}{p} \lt 100 \$ and any remaining factors are too small or that \$p \gt 999\$ and we have a factor that is too large. So we can discard \$k\$ and decrement \$c\$ by one to form the next smaller palindrome, eg. \$k=996699\$, and keep trying smaller palindromes.

If you reach \$p\lt \min\left(\frac{k}{100}, 999\right) \$ without finding any prime that evenly divides \$k\$ we need to convince ourselves that the remaining factors can be multiplied into two factors so that both factors are three digits.

There are a few ways to convince ourselves of the above. One way is trial division by simply trying all divisors \$d\$ such that \$100\le d \le \max\left(\frac{k}{100}, 999\right)\$ and checking what the other factor is.

Another more elegant way is to use the fact that we know that there is no prime factor larger than \$p\le\min\left(\frac{k}{100}, 999\right)\$ and find the largest prime factor \$p_{max}\le\min\left(\frac{k}{100}, 999\right)\$ and let \$r_i = \frac{k}{p_{max}}\$.

Let the prime factors of \$r_i\$ be \$p_i\$ and let \$Q=\prod_{\forall i:p_i>\frac{999}{p_{max}}}p_i\$. At this point you have the largest prime factor of \$k\$ as \$p_{max}\$ and all prime factors of \$r_i=\frac{k}{p_{max}}\$ that are too big to be together with \$p_{max}\$ multiplied together as \$Q\$.

Now, factor \$\frac{r_i}{Q}\$ into primes \$P_k\$. Each of the \$P_k\$ primes has to be multiplied into either \$Q\$ or \$p_{max}\$. Iteratively try all combinations (and exit early for impossible branches) until you find one that is satisfactory or retry next smallest palindrome if no combination was found.

Note: This may well be slower than trial multiplication but it's another way to approach the problem and it may give birth to other ideas.

Answer 3

In addition to Mike Nakis's great suggestions, I think the IsPalindrome function can be made more simple and readable like this:

static bool IsPalindrome(long testNumber)
{
    var stringRepresentation = testNumber.ToString("d");

    return stringRepresentation == Reverse(stringRepresentation);
}

private static string Reverse(string stringRepresentation)
{
    var charArray = stringRepresentation.ToCharArray();
    Array.Reverse(charArray);

    return new string(charArray);
}

This also reduced the total execution time on my machine from 416ms to 246ms.

Answer 4

I second @MikeNakis.
Additionally:

If you only want the largest, why not check from the top down? Just mind the pitfall that the first found might not be the largest.
(583 x 995 = 580085; 517 x 995 = 514415; 913 x 993 = 906609; 121 x 991 = 119911)

private int? GetLargestNumericPalindrome(int minBound, int maxBound) {
    int largestFound = minBound - 1;
    for (int i = maxBound; i >= minBound; i--) {
        // "taking advantage of the fact that A*B = B*A"
        // So we don't need to check N*maxBound since we already checked maxBound*N...
        // So only checking from N*N downwards.
        for (int k = i; k >= minBound; k--) {
            int num = i*k;
            if (num <= largestFound) {
                break; // Any other values of k for this i will also be lower.
            }
            if (IsPalindrome(num)) {
                largestFound = num;
                if(k > minBound) {
                    // Black magic. Prove with logic and THEN uncomment this next line.
                    //minBound = k;
                }
                break;
            }
        }
    }
    if(largestFound < minBound) {
        return null;
    }
    return largestFound;
}

private bool IsPalindrome(int num) {
    // Use OP's implementation.
    // Consider @MikeNakis's comments.
    throw new NotImplementedException();
}

Answer 5

Building on @Neves, but filtering with multiples of 10 and leveraging the inner for loop to reduce multiplications:

private int? GetLargestNumericPalindrome(int minBound, int maxBound) {
    int largestFound = 0;
    for (int i = maxBound; i >= minBound; i--) {
        // Normally, numbers don't have leading zeros, 
        // so palindromes don't have trailing zeros.
        // Testing this up front seems worthwhile (almost a 10% improvement?).
        if (i % 10 == 0) {
            continue;
        }
        int smallestWorthChecking = i * minBound;
        if (smallestWorthChecking <= largestFound) {
            smallestWorthChecking = largestFound + 1;
        }
        // "taking advantage of the fact that A*B = B*A"
        // So we don't need to check N*maxBound since we already checked maxBound*N...
        // So only checking from N*N downwards.
        for (int num = i*i; num >= smallestWorthChecking; num -= i) {
            // ... palindromes don't have trailing zeros.
            if (num % 10 != 0 && IsPalindrome(num)) {
                largestFound = num;
                break;
            }
        }
    }
    if(largestFound == 0) {
        return null;
    }
    return largestFound;
}

synthesizing ideas from @MikeNakis -- no need to reverse/match the whole, and @SteveB -- keeping it numeric

static bool IsPalindrome(long testNumber)
{
    var reversed = 0L;
    var forward = testNumber
    while (reversed < forward)
    {
        var digit = forward % 10;
        reversed = reversed * 10 + digit;
        forward = forward / 10;
    }
    // Here, reversed can have at most 1 more digit than forward
    // Test for even palindromes, forward and reversed identical,
    // or odd palindromes, reversed adds 1 extra digit
    return forward == reversed || forward == reversed / 10;
}

Answer 6

I am kind of thinking like SteveB

I think that you should shorten up your code a little bit and make it straight to the point

    static void Main(string[] args)
    {
        long result = 0;

        for (int i = 100; i < 1000; i++)
        {
            for (int k = 100; k < 1000; k++)
            {
                if (IsPalindrome(i * k))
                    if ((i * k) > result)
                        result = i * k;
            }
        }

        Console.WriteLine(result);
    }

could become this

static void Main(string[] args)
{
    long result = 0;

    for (int i = 100; i < 1000; i++)
    {
        for (int k = 100; k < 1000; k++)
        {
            int product = i * k;
            if (IsPalindrome(product) && product > result)
            {    
                 result = product;
            }
        }
    }
    Console.WriteLine(result);
}

And then I would turn that into a function so that you are not doing all this work in the Main Method

public int largestPalindrome(int smallNumber, int largeNumber)
{
    int result = 0;

    for (int i = smallNumber; i < largeNumber; i++)
    {
        for (int k = smallNumber; k < largeNumber; k++)
        {
            int product = i * k;
            if (IsPalindrome(product) && product > result)
            {
                result = product;
            }
        }
    }
    return result;
}

Then you just call this in your Main Method

static void Main(string[] args)
{
    int bigPalindrome = largestPalindrome(100,1000);
    Console.WriteLine(bigPalindrome.ToString());
}

I changed everything to int type because with a max of 1000*1000 you won't break 2,147,483,647 and because you aren't going negative then you could actually use an unsigned integer and double the result size.

for this simple exercise you only need an integer.

---

you can use the functions without adding scope classifiers as long as they are in the same class