Another one of those missing numbers puzzles.
You are given a stream of n numbers, consisting of the integers 1,2,…,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(logn) 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,…,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(logn) 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