[Leet Code Top 100] #338. Counting Bits

문제 정보

• Leet Code 문제 링크
• 난이도 : Easy

 

해결 방법

첫 번째로 시도한 방법은 1 의 개수를 구하는 방법은 n >> 1 을 반복해서 첫번째 bit 에서 갯수를 세는 것 입니다. n >> 1 의 시간복잡도가 log n 이기 때문에 총 시간복잡도는 O(n log n) 입니다.

두 번쨰로 시도한 방법은 Dynamic Programming 으로 점화식은 getOnes(n) = 1 + getOnes(n - maxBitNum(n)) 입니다.

세 번째는 Discuss 탭에 있던 글을 참고했는데 두 번째와 비슷한 방법이지만 반대로 maxBitNum 을 따로 구하지 않고 >> 1 로 비트를 shift 한 뒤 첫 번째 자리의 갯수를 세는 방법입니다. Follow up 조건을 만족합니다.

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++)?

 

소스 코드

// Leet Code
// #338. Counting Bits
// Success
// Runtime: 141 ms, faster than 36.13% of JavaScript online submissions for Counting Bits.
// Memory Usage: 44.5 MB, less than 87.04% of JavaScript online submissions for Counting Bits.

function main(){
    // Input // Output
    n = 5; // [0,1,1,2,1,2]

    console.log(countBits(n));
}

/**
 * @param {number} n
 * @return {number[]}
 */
// var countBits = function(n) {
//     const result = [];
//     const getOnes = function(n){
//         let result = 0;
//         while(0 < n){
//             if(n & 1) result++;
//             n = n >> 1;
//         }
//         return result;
//     }

//     for(let idx = 0; idx <= n; idx++){
//         result.push(getOnes(idx));
//     }

//     return result;    
// };

// var countBits = function(n) {
//     const result = [];

//     const maxBitNum = function(n){
//         let result = 1;
//         while(true){
//             if(n < result * 2){
//                 break;
//             }
//             result *= 2;
//         }
//         return result;
//     }

//     const getOnes = function(n){
//         if(n === 0) return 0;
//         if(n === 1) return 1;

//         console.log(`n:${n} / n(2):${n.toString(2)} / maxBitNum(n):${maxBitNum(n)}`);
//         return 1 + getOnes(n - maxBitNum(n));
//     }

//     for(let idx = 0; idx <= n; idx++){
//         result.push(getOnes(idx));
//     }

//     return result;    
// };

var countBits = function(n) {
    const result = [0];
    
    for(let idx = 1; idx <= n; idx++){
        result[idx] = result[idx >> 1] + (idx & 1);
    }

    return result;    
};

main();

 

참고 자료

• LeetCode Top 100 Problem Selection
• LeetCode - typescript + javascript - 3 line o(n) beats 100% - w/ VERY DETAILED explanation