I was working on the codewars kata Integers: Recreation One:
1, 246, 2, 123, 3, 82, 6, 41
are the divisors of number246
. Squaring these divisors we get:1, 60516, 4, 15129, 9, 6724, 36, 1681
. The sum of these squares is84100
which is290 * 290
.Task
Find all integers between
m
andn
(m
andn
integers with1 <= 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;
}
You can make at least two savings:
The inner loop could identify both $num
as $i / $num
as divisors, and then you can exit the loop earlier -- when $num
exceeds the square root of $i
You don't need to store those squared divisors in an array: you can immediately add them to $sum
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;
}