Count the ones in every number from 0 to n. Each answer is the count for i shifted right one bit, plus its last bit.
▼The problem
LeetCode 338 (Easy). Given an integer n, return a list ans of length n + 1 where ans[i] is the number of 1 bits in the binary form of i, for every i from 0 to n.
Example (LeetCode's second): n = 5 → [0, 1, 1, 2, 1, 2].
The solution
def countBits(n):
ans = [0] * (n + 1)
for i in range(1, n + 1):
ans[i] = ans[i >> 1] + (i & 1)
return ansTranscript
Counting Bits. Given a number n, return a list where entry i is the number of one bits in i, for every i from zero to n.
Take n equals five. Zero has no ones. One, two and four have one each. Three and five have two. The answer is zero, one, one, two, one, two.
The simple way counts each number on its own, digit by digit. That's about log n steps per number, so n log n in all, and it never reuses a count.
Here's the trick. Shift i right by one, and its last bit falls off. What's left is i over two, a smaller number already in the list. So copy that row, then add one bead if i is odd. Take six, one one zero. Drop the zero: three, with two beads. Six is even, so two.
The code is one loop. Start with zeros. For each i from one to n, its entry is the entry for i shifted right by one, plus i AND one. Using i AND i minus one, which clears the lowest one bit, works too.
Let's build the rack up to eight. One copies zero, plus a bead. Two copies one. Three copies one, plus a bead. Four copies two. Five copies two, plus one. Six copies three. Seven copies three, plus one. Eight copies four: just one bead.
Each entry is one lookup and one add, so the time is linear, and the only space is the answer.
Drop the last bit, copy the row, add it back. That's Counting Bits.