HiveBrain v1.2.0
Get Started
← Back to all entries
patterncsharpModerate

Determining numeric palindromes

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
palindromesdeterminingnumeric

Problem

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  result)
                            result = i * k;
                }
            }

            Console.WriteLine(result);
        }

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

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

            List reverseList = new List(list);
            reverseList.Reverse();

            bool palindrome = true;

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

            return palindrome;
        }
    }
}

Solution

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

Context

StackExchange Code Review Q#7502, answer score: 13

Revisions (0)

No revisions yet.