1
\$\begingroup\$

This is my naive approach:

$sample1 = [3, -20, 1, -19, -4, 6, 77, -1, 0, 6];
$sample3 = [4, 5, -7, 0, 2, 44, -3, -5, 66, -7];
$sample4 = [4, 25, 1, 6, 9, 5, 999, 4, 43, 2];

$sample2 = [];
for ($i = 0; $i < mt_rand(10, 30); $i++) {
  $sample2[] = mt_rand(-1000, 1000);
}

extractNumbersThatSquaresAreGreaterThan($sample1);
extractNumbersThatSquaresAreGreaterThan($sample2);
extractNumbersThatSquaresAreGreaterThan($sample3);
extractNumbersThatSquaresAreGreaterThan($sample4);

var_dump($sample1);
//var_dump($sample2);
var_dump($sample3);
var_dump($sample4);

function extractNumbersThatSquaresAreGreaterThan(&$list, $boundary = 26) {
  foreach ($list as $key => $value) {
    if (pow($value, 2) <= $boundary) {
      unset($list[$key]);
    }
  }
}

Any hints for optimization? Is it possible, I've tried few, but in the end it was more complicated (and slower) solution

\$\endgroup\$
2
  • \$\begingroup\$ Please fix the code \$\endgroup\$ – Your Common Sense Jun 26 '18 at 12:39
  • \$\begingroup\$ @YourCommonSense please provide me more test data, than I'll fix \$\endgroup\$ – Codium Jun 26 '18 at 13:13
2
\$\begingroup\$

Hints? Ok.

  1. Don’t square the values, O(n), instead square-root the boundary. You’ll need an or in your test, though.

  2. Don’t unset values in the list. That requires shifting values in memory. Make a new list of same size, fill in values, without gaps, and then resize result.

\$\endgroup\$
1
\$\begingroup\$

I don't know about how fast this solution will be, but anyway I suggest to use functional approach to solve your problem. At least you will have concise code:

$sample4 = [4, 25, 1, 6, 9, 5, 999, 4, 43, 2];

var_dump(extractNumbers($sample4, 26));

function extractNumbers($list, $boundary) {
    return array_filter($list, function($x) use ($boundary) {
        return ($x * $x) > $boundary;
    });
}
\$\endgroup\$
1
\$\begingroup\$

Instead of remove items with unset, I would use array_filter. And in fact, you could factor out the pow function, if you use basic maths.

$$ num^2 \leq boundary\\ \implies |num| \leq \sqrt{boundary} $$

combining this would result in

function extractNumbersThatSquaresAreGreaterThan(&$list, $boundary = 26) {
    $sqrt_boundary = sqrt($boundary);
    $list = array_filter($list, function ($item) use ($sqrt_boundary) {
        return abs($item) > $sqrt_boundary;
    });
}

In addition, I would avoid the use of referenes for this task and just return your value.

function extractNumbersThatSquaresAreGreaterThan($list, $boundary = 26) {
    $sqrt_boundary = sqrt($boundary);
    return array_filter($list, function ($item) use ($sqrt_boundary) {
        return abs($item) > $sqrt_boundary;
    });
}
\$\endgroup\$
1
  • \$\begingroup\$ Thanks a lot for this. Especially reminding me, that something like ABS exists ;) \$\endgroup\$ – Codium Jun 30 '18 at 19:18

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.