14 April 2022

Four is magic and Equilibrium Indices

Four is magic

Not much to say about this, really. Someone will have a one-line answer, but as usual I prefer readability to conciseness.

It's a little hard to see what practical use this might be!

Equilibrium indices

If we were guaranteed that the numbers were sorted in ascending order we could do a binary chop to get to the answer, but we're not, so I can see little alternative to starting at the second member of the array and working through to the second last.  It's the second, because the statement of the problem suggest that the two subarrays are not null.

I suppose you save a few nanoseconds by doing something like this:

$left_sum = $array[0];
$right_sum = sum of $array[2] to the end;

and then loop over the array elements, adding the element to $left_sum, and subtracting it from $right_sum, but really, that's a bit messy and for any reasonable array it won't take long just to recreate $left_sum and $right_sum each time. So that's what I did.

I noted that It doesn't say positive or non-zero integers, so we'd better allow for zero and negative ones, which means that there may not be a unique answer (eg 4, 5, 0, 0, 4, 5 or -3, 3, 0, -4, 4, 0, -5, 5).

No comments:

Post a Comment