Computer Scientists Invent an Efficient New Way to Count | Quanta Magazine

Wow, this is a fun algorithm to get an approximation of the number of unique elements in a list.

Next, move to Round 2. Continue as in Round 1, only now we’ll make it harder to keep a word. When you come to a repeated word, flip the coin again. Tails, and you delete it, as before. But if it comes up heads, you’ll flip the coin a second time. Only keep the word if you get a second heads. Once you fill up the board, the round ends with another purge of about half the words, based on 100 coin tosses.

This is the kind of problem that programmers, particularly those working at scale, have to deal with fairly regularly. It seems easy "well, just count the things", but counting, particularly unique things, in a list that is billions or billions of billions long is very resource intensive. And often an approximate count is fine.