C# : Find the largest palindromic number made from product of 3-digit numbers

Question

I'm writing a program to find the largest palindromic number made from product of 3-digit numbers. Firstly,i Create a method which has ability to check if it is a palindromic number. Here is my code :

static int check(string input_number)
{
    for (int i = 0; i < input_number.Length/2; i++)
        if (input_number[i] != input_number[input_number.Length - i])
            return 0;
    return 1;
}

After that, it's my main code:

static void Main(string[] args)
{
    int k = 0;
    for (int i = 0; i < 999; i++)
        for (int j = 0; j < 999; j++)
        {
            k = i * j;
            if (check(k.ToString()) == 1)
                Console.Write(k + "      ");
        }
}

But when it has a problem that the length of input_number is zero. So my code doesn't run right way. What can I do to solve the length of input_number?

Answer 1

You have a few bugs in your code:

1. 3-digit-numbers range from `100` to `999`, not from `0` to `998` as your loops currently do.

So your Main method should look like this:

static void Main(string[] args)
{
    int k = 0;
    for (int i = 100; i <= 999; i++)
        for (int j = 100; j <= 999; j++)
        {
            k = i * j;
            if (check(k.ToString()) == 1)
                Console.Write(k + "      ");
        }
}

Now all pairs of three digit numbers are checked. But to improve performance you can let j start at i, because you already checked e.g. 213 * 416 and don't need to check 416 * 213 anymore:

for (int i = 100; i <= 999; i++)
    for (int j = i; j <= 999; j++) // start at i

And since you want to find the largest, you may want to start at the other end:

for (int i = 999; i >= 100; i--)
    for (int j = 999; j >= 100; j--)

But that still does not guarantee that the first result will be the largest. You need to collect the result and sort them. Here is my LINQ suggestion for your Main:

var results = from i in Enumerable.Range(100, 900)
                    from j in Enumerable.Range(i, 1000-i)
                    let k = i * j
                    where (check(k.ToString() == 1)
                    orderby k descending
                    select new {i, j, k};
var highestResult = results.FirstOrDefault();

if (highestResult == null)
    Console.WriteLine("There are no palindromes!");
else
    Console.WriteLine($"The highest palindrome is {highestResult.i} * {highestResult.j} = {highestResult.k}");

2. Your palindrome-check is broken

You compare the character at index i to input_number[input_number.Length - i], which will throw an IndexOutOfRangeException for i = 0. Strings are zero-based index, so index of the last character is Length-1. So change the line to

if (input_number[i] != input_number[input_number.Length - i - 1])

Finally, I suggest to make the check method of return type bool instead of int:

static bool check(string input_number)
{
    for (int i = 0; i < input_number.Length/2; i++)
        if (input_number[i] != input_number[input_number.Length - i - 1])
            return false;
    return true;
}

This seems more natural to me.

Answer 2

You can use method below. Because you are trying to find the largest number you start from 999 and head backwards, do multiplication and check if its palindrome.

private void FindProduct()
{
 var numbers = new List<int>();
 for (int i = 999; i > 99; i--)
 {
    for (int j = 999; j > 99; j--)
    {
        var product = i * j;
        var productString = product.ToString();
        var reversed = product.Reverse();
        if (product == reversed)
        {
               numbers.Add(product);
        }
     }
   }
   Console.WriteLine(numbers.Max());
}