4
\$\begingroup\$

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);
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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);
\$\endgroup\$
  • \$\begingroup\$ With && $i*$i > $found in your outer loop test, you add 80-odd comparisons to the outer loop, but save 800-odd iterations of the outer loop, and 800-odd false starts of the inner loop. Perhaps it is only savings of a millisecond or two, but I'd claim it is still the right thing to do. \$\endgroup\$ – AJNeufeld Oct 4 '18 at 21:03
  • \$\begingroup\$ It's a programmers choice, I prefer to keep the code simple and readable rather than gaining a 2% in time. In my (quick and dirty) benchmarks it doesn't even shows this 2% gain... \$\endgroup\$ – David Lemon Oct 5 '18 at 8:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.