Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Reuse the count after removing one set bit: The Bit Census.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Counting bits matches the clues
- 2Keep this true after every move: counts[value] is the exact number of set bits for every processed value
- 3Reach the result within O(n) time and O(n) output space
Rules and pressure
- Target cost: O(n) time and O(n) output space
- State rule: counts[value] is the exact number of set bits for every processed value
Lesson 1 of 3
Live algorithm trace
Counting bits
Complete execution1 of 5
Seed zero with no one-bits.
1
counts[0] = 02
for value from 1 through n3
smaller = value & (value - 1)4
counts[value] = counts[smaller] + 15
return countscounts = [0]
Truth to preserve / Cost target
Truth to preserve
counts[value] is the exact number of set bits for every processed value
Cost target
O(n) time and O(n) output space
Clearing the lowest set bit maps each positive integer to a smaller number whose answer is already known. Add one for the bit that was removed.
Your call · What should guide every step of this algorithm?