Sum the remainders of ai%aj given an array "a"

Question

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<$len; $i++)
 for($j=0; $j<$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.

• snehm: One possible optimisation is to eliminate duplicates, instead keep total count for each duplicate. Other possible optimisation is to sort this array, now to calculate remainder for ai you will need to perform modulo operation on higher numbers only as smaller numbers are indeed remainder simply count them. This will reduce time comlexity by half by order remains same :(

Answer 1

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.

• Prashanth kumar: "foreach is faster than a for-loop" thanks for this pointer. I tried following your suggestions, but the same is failing on bigger inputs
• insertusernamehere: @Prashanthkumar For which inputs is it failing? What is the maximum execution time for PHP?
• insertusernamehere: Also, one might think, that this will increase performance: if ($a === $b) continue; if ($a < $b) { $sum += $a; continue; } $sum += $a % $b; But when running the tests, this was always slower than a simple $sum += $a % $b;.