Project Euler : Problem 4

Problem 4 on Project Euler is this:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 x 99.

Find the largest palindrome made from the product of two 3-digit numbers.

First we need a function to check whether a number is palindromic. In fact we will create a generic function to check whether a given string is palindromic. This is the Delphi code:

function TfrmMain.isPalindrome(s : string) : boolean;
  result := (s = ReverseString(s));

Given a string s, it creates a reversed version of that string using the Delphi function ReverseString. If the resulting string is equal to the original string then the original string is palindromic.

A brute-force approach would be to calculate the result of multiplying all the numbers from 999 to 100 by all the numbers from 999 to 100, seeing which of these are palindromic and then retrieving the largest number from these results. This would need 900 times 900 (810000) multiplications, then each of these numbers would need to be checked for being palindromic. I initially used this approach and it still produced the result in under a minute (which is the basic criteria for Project Euler solutions).

However, a little thought revealed that if we keep a record of the largest palindrome found so far, we do not have to check every multiplication for being palindromic. We only need to check those products where the current product is greater then the current largest palindrome. This is the resulting code:

procedure TfrmMain.Problem4;
  num1, num2, maxNumber:integer;
  num1 := 999;
  maxNumber := 0;
  while num1 > 99 do begin
    num2 := num1;
    while num2 > 99 do begin
      if num1 * num2 > maxNumber then
        if isPalindrome(IntToStr(num1 * num2)) then maxNumber := num1 * num2;

We initialise the first number(num1) to 999 in line 5 and the best result so far (maxNumber) to 0 at line 6; The outer while loop runs from 999 down to 100, and the inner loop runs from the value of num1 down to 100. If the result of the multiplication is greater then the current maximum (line 10), the result is checked, and if palindromic the maximum value is replaced by this value (line 11).

This code produces the correct result in under a second.

Tags: , ,

Comments are closed.