A stream of items is read once, from left to right. Using only a constant number of memory words, find an item that occurs more than times, assuming such an item exists. Then explain how a second pass can check whether a majority exists at all.
A stream of items is read once, from left to right. Using only a constant number of memory words, find an item that occurs more than times, assuming such an item exists. Then explain how a second pass can check whether a majority exists at all.