Counting Bits — DP with Bit Trick
Sanjeev SharmaAdvertisement
Problem
Return an array where ans[i] = number of 1s in binary representation of i, for 0 <= i <= n.
Approach — DP
dp[i] = dp[i >> 1] + (i & 1). Shifting right removes last bit; adding i & 1 accounts for it.
Time: O(n) | Space: O(n)
Solutions
Python
class Solution:
def countBits(self, n: int) -> list[int]:
dp=[0]*(n+1)
for i in range(1,n+1): dp[i]=dp[i>>1]+(i&1)
return dp
C++
class Solution {
public:
vector<int> countBits(int n){
vector<int> dp(n+1,0);
for(int i=1;i<=n;i++) dp[i]=dp[i>>1]+(i&1);
return dp;
}
};
Java
class Solution {
public int[] countBits(int n){
int[] dp=new int[n+1];
for(int i=1;i<=n;i++) dp[i]=dp[i>>1]+(i&1);
return dp;
}
}
Complexity
- Time: O(n) | Space: O(n)
Advertisement
← Previous
Reverse Bits — 32-Bit Reversal