Gamified challenge · Dynamic programming
A display shows a number in binary with bulbs: a lit bulb is a 1, a dark bulb a 0. It counts up from 0 to n.
Write countBits(n) (Python: count_bits(n)) that returns a list of n + 1 numbers, where item i is the number of lit bulbs (1-bits) of i. For n = 5 the answer is [0, 1, 1, 2, 1, 2] (0, 1, 10, 11, 100, 101).
Counting each number from scratch works; the neat answer reuses an earlier count, so each item takes O(1).
This game is part of the paid plans. Sign in, then pick a plan to write your answer, watch it play out, and step through the algorithm with its guide.
Sign in with Google