[JAVA] 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++)?

아이디어

- 짝수(2, 4, 6, 8...) 의 바이너리는 10, 100, 110, 1000과 같다. 여기서 중요한 점은 항상 마지막이 0으로 끝나는것.

- 즉, >> 연산을 사용하여, 1비트 쉬프트 연산을 하였을 때 (= 2로 나누었을 때) 바이너리 문자열 1의 갯수는 변함이 없다는 것이다.

 

- 반대로 홀수의 경우, 1비트 쉬프트 연산을 하였을 때, 원래 이진 문자열에서 항상 '1' 하나가 없어지므로, '1' 하나를 항상 보정해주어야 한다.

 

- 결론적으로, 짝수의 경우, 바이너리 문자열 1의 갯수는 반으로 나눈 수와 같으며, 홀수의 경우 1 작은 짝수의 갯수에 1개를 더한 수와 같다.

풀이

public int[] countBits(int num) {
    int[] f = new int[num + 1];
    
    for (int i=1; i<=num; i++){
    	//f[i] = f[i / 2] + i % 2
    	f[i] = f[i >> 1] + (i & 1);
    }
    return f;
}

참고

f[1] = (f[0]==0) + (1%1==1) = 1
f[11] = (f[1]==1) + (11%1==1)  = 2
f[110] = (f[11]==2) + (110%1==0) = 2
f[1101] = (f[110] ==2) + (1101%1==1) =3;
...

즉 f[i] = f[i/2] + i%2

다른 풀이

비트 연산 없는 풀이

public class Solution {
    public int[] countBits(int num) {
    
        int[] answer = new int[num+1];
        int offset = 1;
        
        for(int i = 1; i < answer.length; i++){
            if(offset * 2 == i) offset *= 2;
            answer[i] = 1 + answer[i - offset];
        }
        
        return answer;
    }
}