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.
Top comments (0)