Counting Bits
Easy· bit counting· DP
Problem
Given n, return an array of length n + 1 where the value at index i is the number of 1 bits in i. Aim for a single linear pass rather than counting each number from scratch.
Examples
Input: n = 2
Output: [0,1,1]
Input: n = 5
Output: [0,1,1,2,1,2]
Constraints
- • 0 <= n <= 10^5
Hints & approach
Hint 1
Relate the bit count of i to that of a smaller number you already computed.
Hint 2
Shifting i right by one drops only its lowest bit.
Hint 3
bits[i] = bits[i >> 1] + (i & 1).
Approachtry the hints first
Build the answer from smaller values. The number i >> 1 has the same bits as i except the last one, so bits[i] = bits[i >> 1] + (i & 1). An equivalent recurrence is bits[i] = bits[i & (i - 1)] + 1. Either way each entry costs O(1).
Time O(n) · Space O(1) besides the output