Problem 4

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.

Initial Thoughts:
As usual this problem has a couple of different layers to it. The first order of business is to figure out how to reverse a number and then compare it to the original number. The second order of business is to test each number from 100 to 999.

Multiplying the two digits is the easy part of this question, I'll just nest a for loop in another to multiply x by y until y hits 999, then increase x once and start over for y. Checking the product of x and y to determine if it is a palindrome is the difficult part.

My breakthrough came after a bit of brainstorming and bouncing some questions off of a friend. His hint of write down a sample palindrome down on paper and really thing about the steps you do to reverse the number by hand. So what I do of course is on a new line and take the last digit and write it down first on this new line. I then add the next to last digit to the new line and so one until the end of the number. Then compare the two numbers. Now obviously you can eyeball it and tell instantly when it's down on paper, but really stepping back these are the steps one is taking.

This means I will need to know the length of the product of x and y and create a loop to take the last digit and add that digit to a new variable (the "new line") until I run out digits. I will also need to multiply the number I moved by 10^(remaining digits in the original string) to keep the correct power of the number. It occurs to me that I could attempt to convert each number into a string and reverse the string, but what's the fun in that? I'm going to complete this problem via math related functions only. If you prefer converting to a string first you can find many options by searching for "reverse a string in c#". Easiest solution I saw was to store the string as an array then reverse the array. Done.

Final Thoughts:
In the end this problem becomes easy once you realize you can use mod to move the decimal place over to the left and keep the remainder. Multiply this remainder by 10^(however many digits are left), store the new number as a variable, then compare. Each step check to see if the number is a palindrome then store the number if it is greater than the last successful palindrome.

The code takes about 1.3 seconds to run - which I'm not thrilled with but is still well under the one minute time limit set by PE. I'm still curious if there is a way to speed this up. I know that if either x or y end in a zero the resulting number will not be a palindrome. I never implemented this however as at most I'd expect a 10% gain.

Solution Code:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int x = 1;
            int y = 1;
            double z = 0;
            double prodxy = x*y;
            double varlen = Math.Ceiling(Math.Log(prodxy) / Math.Log(10));  //Finds the length of the number
            double paldr = 0;
            double maxpaldr = 0;
            int maxx = 0;
            int maxy = 0;

            Stopwatch stopWatch = new Stopwatch();
            stopWatch.Start();
            for (x = 100; x < 1000; x++)
            {
                for (y = 100; y < 1000; y++)
                {
                    prodxy = x * y;
                    varlen = Math.Ceiling(Math.Log(prodxy) / Math.Log(10)); //Finds the length of the number
                    paldr = 0;
                    for (z = varlen; z > 0; z--)
                    {
                        paldr = paldr + ((Math.Pow(10, z - 1)) * (prodxy % 10));
                        prodxy = Math.Floor(prodxy / 10);
                    }
                    if (paldr == (x * y) && paldr > maxpaldr)
                    {
                        maxpaldr = paldr;
                        maxx = x;
                        maxy = y;
                    }
                }
            }

            stopWatch.Stop();

            Console.WriteLine("Answer: " + maxx + " * " + maxy + " = " + maxpaldr);
            Console.WriteLine("Elapsed Time: " + stopWatch.ElapsedMilliseconds + " ms");
        }
    }
}