Counting Bits
Easy· bit counting· DP
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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
