Count (distinct) problem

Cosmin Negruseri
24 octombrie 2012

Here's a neat problem from Alexandru Andoni:

You're given a 1GB file containing 64 bit integers.
Come up with an algorithm which estimates the number of distinct integers in the file. You're allowed to use 1024 bytes of memory and you can read the file only once.
How good is your estimation?