(Leet Code c++)Counting Bits

338. Counting Bits

 

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.

 

Example 1:

Input: n = 2 Output: [0,1,1] Explanation: 0 --> 0 1 --> 1 2 --> 10

Example 2:

Input: n = 5 Output: [0,1,1,2,1,2] Explanation: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101

 

Constraints:

• 0 <= n <= 105

 

Follow up:

• It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
• Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

DP를 통한 문제 풀이.

우선 n + 1 길이의 int형 벡터를 선언한 후, 0으로 초기화 한다.

 

n이 0인 경우 바로 dp 벡터를 리턴하도록 한다.

 

n이 1 이상인 경우,

DP 알고리즘을 통해 1의 개수를 저장할 수 있다.

dp[1] = 1로 시작을 한 후,

for문을 통해 2 ~ n까지 실행한다.

 

i가 홀수인 경우, 

현재 i의 이진수 1의 개수는 1 + dp[i / 2]에 해당한다.

 

i가 짝수인 경우,

현재 i의 이진수 1의 개수는 dp[i / 2]에 해당한다.

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> dp(n + 1, 0);
        
        if(n > 0){
            dp[1] = 1;

            for(int i = 2; i <= n; i++){
                if(i % 2){
                    dp[i] = 1 + dp[i / 2];
                }
                else{
                    dp[i] = dp[i / 2];
                }
            } 
        }
        
        return dp;
    }
};