Solving number of distinct elements in $O(\frac{n\ell}{p})$ space complexity with $2p$ passes over data Suppose there is an n-element stream with elements from $\{0,1\}^\ell$ which means each element is in set $\{0, \dots , 2^\ell-1\}$. Also may assume $2^\ell &gt;n^2$. How can I with $2p$ passes over the data (for $p \in \{1, \dots , 2^\ell\} $) solve the number of distinct elements problem using only $O(\frac{n}{p}\ell)$ bits of memory? Not looking for probabilistic algorithms.
Try something along the following lines. Preform $p$ iterations where each iteration consists of two passes over the stream. The $i$'th iteration first pass remembers all elements whose index $\bmod p$ equals $i$ , denote this collection by $S_i$. The second pass, for each element of the stream whose index $\bmod p$ is greater than $i$, checks if it appears in $S_i$, and if so deletes it. Denote by $S_i'$ the remaining subset after the second pass, then your algorithm returns $\sum\limits_{i=1}^p |S_i'|$.