Given a number n, build an array where result[i] is the number of 1-bits in i's binary form. For one number, you'd count bits in O(32). For n numbers... that's O(32n). Can you do better?

Every CS student learns to count bits the hard way — mask and shift, 32 times per number. It is the kind of loop you write once in an interview and never think about again. But what if you need the popcount for EVERY number from 0 to n? Running 32 iterations per number suddenly feels expensive. There might be structure hiding in the binary representations that makes this cheaper. Let's find out by counting a few by hand.