[LeetCode] 338. Counting Bits (C++)

문제

 

https://leetcode.com/problems/counting-bits/

Counting Bits - LeetCode

 

풀이

 

난이도: Easy

 

 

위의 그림을 보면 알겠지만 

2^k ~ 2^(k+1) -1 의 수들은 k+1 번째 비트가 1이고 나머지는 0 ~  2^k -1와 뒷부분이 완전히 동일하다.

따라서 0 ~  2^k -1의 비트에서 1의 수들에 + 1을 붙인 것이 2^k ~ 2^(k+1) -1의 1의 개수가 된다.

따라서 계산해 둔 수들을 이용하면 선형 탐색으로 O(n)의 시간복잡도에 답을 구할 수 있다.

 

 

비트 연산에 중점을 두어 푼다면 다음과 같이 >>연산자로 더 깔끔히 구현이 가능하다.

vector<int> countBits(int num) {
     vector<int> res(num + 1, 0);
     for (int i = 1; i <= num; ++i) {
         res[i] = res[i >> 1] + (i & 1);
     }
     return res;
}

코드 출처: Four lines, C++, time O(n), space O(n)

 

코드