So here are solutions. To make it easier to read, I'll repeat tasks here. All tasks start with the same statement:
You have an array with integers sequence from 1 to 1000:
[1, 2, 3, 4, 5, ..., 1000]
1. Easy
An item with value x
was removed, so the array became like:
[1, 2, 4, 5, ..., 1000]
Then the array was shuffled. How to find x
in O(n)
time and O(1)
memory?
Solution
Just sum up all items and subtract the result from 500500 (a sum of integers from 1 to 1000 inclusively).
2. Harder
An item with value x
was replaced with x - 1
so the array became like:
[1, 2, 2, 4, 5, ..., 1000]
Then the array was shuffled. Again, you need to find x
in O(n)
time and O(1)
memory.
Solution
Just summing up all elements won't give anything — it'll always be 500499. Is there a way to “amplify” values, so 3–1 will impact the result differently than 495–1? Yes, there is one, and it's just squaring items.
Indeed, was replaced with , which means the result — sum of squares — gets less than expected value by
To find , subtract actual squares sum from expected value — sum of squares of 1 to 1000 which is 333,833,500. Then,
Yes, it's that simple!
3. Hard
An item with value x
was replaced with y
where y
is any integer from 1
to 1000
, so the array became like
[1, 2, 9, 4, 5, ..., 1000]
The array was shuffled, and your task again is to find x
and y
in O(n)
time and O(1)
memory.
Solution
Summing up values or squares won't give anything but what if we do both? We can substitute with where is any integer, possibly negative. To find we sum all items and subtract the result from 500500 which immediately gives . Then we may use a formula similar to one from 2nd problem:
where is the difference of expected and actual squares sum.
And finally,
Top comments (0)