Another one of those missing numbers puzzles.
You are given a stream of $n$ numbers, consisting of the integers $1, 2, \dots, n$, except that two of those are missing, and some other two are repeated.
For example, the stream could be 6,1,4,2,1,4. The numbers 3 and 5 are missing, while 1 and 4 are repeated.
Can you give an algorithm to find out what the four numbers are (missing and repeated) which uses $O(\log n)$ space?
Remember, this is a stream of numbers, so you cannot revisit the numbers you have seen before, unless you store them and that counts towards your space usage.
The total time used must be $O(n)$.
[Solution]
You are given a stream of $n$ numbers, consisting of the integers $1, 2, \dots, n$, except that two of those are missing, and some other two are repeated.
For example, the stream could be 6,1,4,2,1,4. The numbers 3 and 5 are missing, while 1 and 4 are repeated.
Can you give an algorithm to find out what the four numbers are (missing and repeated) which uses $O(\log n)$ space?
Remember, this is a stream of numbers, so you cannot revisit the numbers you have seen before, unless you store them and that counts towards your space usage.
The total time used must be $O(n)$.
[Solution]
No comments:
Post a Comment