2 clarifications 1. Are you allowed to store the numbers ? ( I assume not, else the problem is trivial) 2. If your answer to 1 (above) is "no", then do you want a deterministic or probable answer ?
I found a nice resource on Stream Algorithms, will have to dig into it then :)
Assume the stream of integers is appearing in array 'a'.
ReplyDeleteInitialize -
majority = a[0];
counter = 1;
As the number comes in (i=1 onwards) -
if a[i] == majority -> counter++;
else if counter == 0 -> majority = a[i];
else counter--;
At the end, if there is majority, it is saved in the variable majority.
P.S.: I commented earlier also. But it is now appearing the other post "Server allocation...." Please delete from there.
2 clarifications
ReplyDelete1. Are you allowed to store the numbers ? ( I assume not, else the problem is trivial)
2. If your answer to 1 (above) is "no", then do you want a deterministic or probable answer ?
I found a nice resource on Stream Algorithms, will have to dig into it then :)