## DEV Community

Aleksei Berezkin

Posted on • Updated on

# Solution to algorithms exercise

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

$d = x^2 - (x - 1)^2 = \newline = x^2 - x^2 + 2x - 1 = \newline = 2x - 1$

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

$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]


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

$d = x^2 - (x - k)^2 = \newline = x^2 - x^2 + 2kx - k^2 = \newline = 2kx - k^2 = \newline = k(2x - k),$

where $d$ is the difference of expected and actual squares sum.

And finally,

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