Algorithms exercise: “find removed sequence item” and more

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?

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.

3. Hard

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

or

[872, 2, 3, 4, 5, ..., 1000]

or even

[1, 2, 3, 4, 5, ..., 999, 214]

As usually, the array was shuffled, and your task is to find x and y in O(n) time and O(1) memory.

Happy coding!

Answers will be published soon.