Data Structures & Algorithms › Bit Manipulation
💡
Exercise 155

Counting Bits 20 XP Easy

LeetCode Ctrl+Enter Run Ctrl+S Save

For every number i in [0, n], count the number of 1-bits. Return as an array.

# DP approach: dp[i] = dp[i >> 1] + (i & 1) # i>>1 is i with last bit removed # i&1 is the last bit itself

This gives O(n) time vs O(n log n) if we count bits for each number individually.

💡 Pro tip: Understand this problem deeply — don't just memorize the code. Try explaining the approach out loud as if teaching a friend. If you can explain it simply, you truly understand it!

📋 Instructions
Return array of bit counts for 0 to 5.
dp[0]=0. For each i: dp[i] = dp[i >> 1] + (i & 1). You've got this — take it step by step!
🧪 Test Cases
Input
countBits(5)
Expected
[0, 1, 1, 2, 1, 2]
Test case 1
← Previous Next Exercise →
main.py
Hi! I'm Rex 👋
Output
Ready. Press ▶ Run or Ctrl+Enter.
›