[LeetCode] 338. Counting Bits

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

Counting Bits - LeetCode

문제 유형 : 비트마스킹

문제 난이도 : Easy

 

문제

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

 

정수 n이 주어질 때, n+1길이의 0부터 n까지의 2진수 표현에서의 1의 개수를 담은 배열을 구하여라.

 

풀이

오른쪽으로 1비트 이동한 값(절반 이전)의 1의 개수에 i가 홀수인 경우 1을 더하고, 짝수면 더하지 않는다.

 

코드

C++

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> table(n+1, 0);

        for(int i = 1; i <= n; i++) {
            table[i] = table[i >> 1] + (i & 1);
        }

        return table;                
    }
};