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

To find $d$ , 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 $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:

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

And finally,

Hope you enjoyed solving these problems!