13 / 75
Easy
Counting Bits
#13dynamic-programmingbit-manipulation
Return array where result[i] is the number of 1 bits in binary representation of i.
Example:
Input:
n = 5Output:
[0,1,1,2,1,2]Common Mistakes:
- Counting bits for each number individually (O(n log n))
- Not recognizing the DP pattern
- Using Integer.bitCount() without understanding the optimization
Notes:
Key insight: i and i>>1 differ by at most one bit. Relation: ans[i] = ans[i/2] + (i%2). Time: O(n), Space: O(1) excluding output.
💻
Java Solution Hidden
Enable “Show Full Solution” to view the code
Return array where result[i] is the number of 1 bits in binary representation of i.
Example:
Input:
n = 5Output:
[0,1,1,2,1,2]Common Mistakes:
- Counting bits for each number individually (O(n log n))
- Not recognizing the DP pattern
- Using Integer.bitCount() without understanding the optimization
Notes:
Key insight: i and i>>1 differ by at most one bit. Relation: ans[i] = ans[i/2] + (i%2). Time: O(n), Space: O(1) excluding output.
13/75
Counting Bits