DEV Community

Aleksei Berezkin
Aleksei Berezkin

Posted on • Updated on

Solution to algorithms exercise

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]
Enter fullscreen mode Exit fullscreen mode

1. Easy

An item with value x was removed, so the array became like:

[1, 2, 4, 5, ..., 1000]
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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, xx was replaced with x1x - 1 , which means the result — sum of squares — gets less than expected value by

d=x2(x1)2==x2x2+2x1==2x1 d = x^2 - (x - 1)^2 = \newline = x^2 - x^2 + 2x - 1 = \newline = 2x - 1

To find dd , subtract actual squares sum from expected value — sum of squares of 1 to 1000 which is 333,833,500. Then,

x=d+12 x = {d + 1 \over 2}

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]
Enter fullscreen mode Exit fullscreen mode

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 yy with xkx - k where kk is any integer, possibly negative. To find kk we sum all items and subtract the result from 500500 which immediately gives kk . Then we may use a formula similar to one from 2nd problem:

d=x2(xk)2==x2x2+2kxk2==2kxk2==k(2xk), d = x^2 - (x - k)^2 = \newline = x^2 - x^2 + 2kx - k^2 = \newline = 2kx - k^2 = \newline = k(2x - k),

where dd is the difference of expected and actual squares sum.

And finally,

x=12(dk+k)y=xk x = {1 \over 2} \left( {d \over k} + k \right) \newline y = x - k

Hope you enjoyed solving these problems!

Top comments (0)