phpbig-onested-loops

Nested for loops too slow - PHP Codewars Kata Integers: Recreation One


I was working on the codewars kata Integers: Recreation One:

1, 246, 2, 123, 3, 82, 6, 41 are the divisors of number 246. Squaring these divisors we get: 1, 60516, 4, 15129, 9, 6724, 36, 1681. The sum of these squares is 84100 which is 290 * 290.

Task

Find all integers between m and n (m and n integers with 1 <= m <= n) such that the sum of their squared divisors is itself a square.

We will return an array of subarrays or of tuples (in C an array of Pair) or a string. The subarrays (or tuples or Pairs) will have two elements: first the number the squared divisors of which is a square and then the sum of the squared divisors.

Example

list_squared(1, 250) --> [[1, 1], [42, 2500], [246, 84100]]
list_squared(42, 250) --> [[42, 2500], [246, 84100]]

My code passes the basic tests. However, it times out for the final submission. I know this is a nested for loop and seems I am running into a bad Big O, but can't figure out how I can get around it. How can I make this faster?

My code:

function listSquared($m, $n) {
    $results = [];

    for ($i = $m; $i <= $n; $i++) {

        $squared_divisors = [];

        for ($num = 1; $num <= $i; $num++) {
            if ($i % $num === 0) {
                array_push($squared_divisors, ($num * $num));
            }
        }

        $sum = array_sum($squared_divisors);
        $sqrt_sum = sqrt($sum);

        if ((int)$sqrt_sum == $sqrt_sum) {
            array_push($results, [$i, $sum]);
        }
    }

    return $results;
}

Solution

  • You can make at least two savings:

    This leads to this code:

    function listSquared($m, $n) {
        $results = [];
    
        for ($i = $m; $i <= $n; $i++) {
    
            $sum = 0;
            $max = sqrt($i);
            for ($num = 1; $num <= $max; $num++) {
                if ($i % $num === 0) {
                    $sum += $num * $num;
                    $quot = $i / $num;
                    if ($quot > $num) {
                        $sum += $quot * $quot;
                    }
                }
            }
    
            $sqrt_sum = sqrt($sum);
    
            if ((int)$sqrt_sum == $sqrt_sum) {
                array_push($results, [$i, $sum]);
            }
        }
    
        return $results;
    }