Counting Bits

The key idea

Drop the lowest bit of i by shifting right one place: i >> 1. That smaller number was already solved, so ans[i] is just ans[i >> 1] plus the bit you dropped, i & 1. Each answer is built in O(1) from an earlier one.

Problem

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

The straightforward way is to popcount every number independently, but you can do better: the answer for i can be derived in constant time from the answer for a smaller number you already solved. Try to design an algorithm that runs in linear time O(n) and possibly in a single pass using only O(n) space.

Constraints

0 <= n <= 10^5

Examples

Input: n = 2 Output: [0,1,1]

Input: n = 5 Output: [0,1,1,2,1,2]

Complexity

Time: O(n) Space: O(n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →