Solve Project Euler #4 in PHP

Question

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.

<?php

function isPalindrome($input) {
    return (string) $input === strrev($input);
}

$max = 999;
$min = 100;
$found = 0;

for ($i = $max; $i >= $min; $i--) {
    for ($j = $max; $j >= $min; $j--) {
        $result = $i * $j;
        if (isPalindrome($result)) {
            if ($result > $found) {
                $found = $result;
                $a = $i;
                $b = $j;
            }
        }
    }
}

print sprintf("Found %d times %d = %d", $a, $b, $found);

Answer 1

Your outer loop starts at 999 and the inner loop multiplies that by all the numbers from 999 down to 100.

Then your outer loop decrements $i to 998, and the inner loop multiplies that by all the numbers from 999 down to 100. The first test 998*999 has already been considered, since multiplication is commutative. Not a huge inefficiency at this first step, but it gets worse.

When the outer loop gets down to 100, the inner loop again multiplies that by all the number from 999 down to 100 ... only 1 combination which is new.

You should start your inner loop at $i, instead of at $max.

---

Early termination. After finding a palindrome from the product of (say) 901 and 856, you don’t have to test whether the product is a palindrome (expensive operation) unless $result > $found is true (cheap test). And if $result is less than $found, you can break out of your inner loop, since any successive product will be smaller. Finally, if $i * $i < $result (combined with the first optimization), you can also exit your outer loop.

Answer 2

I applied some optimizations from AJNeufeld answer but I would not use the $i*$i optimization as this is already covered by $i*$j on every first inner loop iteration.

I have also done a generalization to increase the number of digits as desired. Here is the code:

<?php

function isPalindrome($input) {
    return (string) $input === strrev($input);
}

function digits($n){
  $min = 10**($n-1);
  $max = $min * 10 - 1;
  return [$min, $max];
}

list($min,$max) = digits(3);

$found = 0;

for ($i = $max; $i >= $min; $i--) {

  for ($j = $i; $j >= $min; $j--) {
    $result = $i * $j;
    if ($result <= $found){
      break;
    }
    if (isPalindrome($result)) {
      $found = $result;
      $a = $i;
      $b = $j;

    }
  }
}

print sprintf("Found %d times %d = %d", $a, $b, $found);