338. Counting Bits - medium
문제
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.
제한사항
- It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n)/possibly in a single pass?
- Space complexity should be O(n).
- Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.
입출력 예
1
2
3
4
5
6
7
Example 1:
Input: 2
Output: [0,1,1]
Example 2:
Input: 5
Output: [0,1,1,2,1,2]
풀이
- DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
vector<int> countBits(int num) {
if(num == 0)
return {0};
else if(num == 1)
return {0,1};
vector<int> res(num + 1, 0);
int carry = 0;
res[0] = 0;
res[1] = 1;
for(int i = 2 ; i <= num ; ++i){
// Pow of 2 는 비트에서 1의 개수가 무조건 1
if((i & (i - 1)) == 0){
res[i] = 1;
carry = i;
}
else{
// i = carry + (i - carry)
// 6 = 4 + 2
// 7 = 4 + 3
// 9 = 8 + 1
res[i] = res[carry] + res[i - carry];
}
}
return res;
}
};