Sum the remainders of ai%aj given an array "a" Given an array of numbers, I am creating a table where, the cell at the intersection of row i and column j contains a number ai % aj.
Numbers in the array can occur multiple times.

Example:
For numbers = [2, 5, 3, 3, 5], the output should be 32.
Here is the table that gets created:

  | 0 1 2 3 4
--------------
0 | 0 2 2 2 2
1 | 1 0 2 2 0
2 | 1 3 0 0 3
3 | 1 3 0 0 3
4 | 1 0 2 2 0


The sum of its elements is 32.

Guaranteed constraints:
1 ≤ numbers.length ≤ 10^5,
1 ≤ numbers[i] ≤ numbers.length.

function sumOfRemainders($numbers) {
    $resSum = 0;
    $len = count($numbers);

    if($len == 1)
        return 0;

    for($i=0; $i&lt;$len; $i++)
        for($j=0; $j&lt;$len; $j++)
            $resSum += $numbers[$i]%$numbers[$j];
    return $resSum;
}


The code works and is of course a brute force approach, but will take huge amount of time for large inputs, or will timeout in case of any testing environment.

How can I possibly make my code faster?
Any suggestions are most appreciated.
A drop in the bucket – but it will increase the performance a little bit at least.

Use foreach instead of for

foreach is faster than a for-loop. So using foreach-loops will decrease the computing time for large inputs. It will also make your function a bit easier, as you don't have to create the $len-variable:

function sumOfRemainders($numbers) {
    $sum = 0;

    if (1 === count($numbers)) {
        return 0;
    }

    foreach ($numbers as $a)
        foreach ($numbers as $b)
            $sum += $a % $b;

    return $sum;
}




Now, for a single run on a small input like your example [2, 5, 3, 3, 5] the difference is neglectable.

However, here a a few benchmarks, when running with large input arrays:

 1000 values  |  original:  0.16s  |  new:  0.08s
 7000 values  |  original:  7.05s  |  new:  4.46s
10000 values  |  original: 14.70s  |  new:  8.84s
20000 values  |  original: 58.67s  |  new: 35.91s


The tests where run with MAMP's PHP 7.2.1 on the CLI on a i7 2.5GHz with 16 GB RAM.



Here are both versions running 5000 values on 3v4l.org:


Original
New version


Unfortunately you can't run more then 5000 values before running into their time limit.

Here's the original script I used for the benchmark.



Basically this is a variant of the Cartesian product. Here's a short read about Efficient Cartesian Product algorithm on Stackoverflow.