Counting Bits - Medium - L
Published:
Question
- https://leetcode.com/problems/counting-bits/
Given an integer num, return an array of the number of 1’s in the binary representation of every number in the range [0, num].
Approach
- DP
Solution
class Solution {
public:
vector<int> countBits(int num) {
if(num == 0)
return vector<int>{0};
vector<int> v(num+1);
v[0] = 0;
v[1] = 1;
for(int i=2; i<=num; i++)
{
v[i] = v[i/2] + ((i%2 == 0)?0:1);
}
return v;
}
};