# Count bits

Đây là bài toán nằm trong series về giải thuật và interview ở các công ty công nghệ.

Đây là một bài toán được xếp ở mức medium trên các trang về chia sẽ đề interview của các công ty công nghệ vì thường khi interview sẽ được yêu cầu tối ưu (thường sẽ dừng ở mức giải quyết bằng dynamic programming)

**Đề: Cho số n. Xuất ra kết quả là một mảng a với mỗi phần tử a[i] là số lượng bits 1 có trong số có giá trị bằng i. với 0<=i<=n.
** Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Input: 5 Output: [0,1,1,2,1,2]

Basic solution: Giải pháp dễ nhất có thể nghĩ đến là đếm từng bits 1 của số đang cần đếm: Độ phức tạp thời gian: O(n*m) với m là số bits dùng để biểu diễn cho số n đầu vào Độ phức tạp không gian: O(n) Nhưng thường khi phỏng vấn ở các công ty công nghệ (google, amazon) thì câu này sẽ yêu cầu tối ưu về thời gian nên thường giải pháp này không được chọn. Nên xem xét giải pháp tốt hơn như dynamic programming bên dưới

int countOnes(int num){
        int count = 0;
        while(num >0){
            count +=(num & 1);
            num=num>>1;
        }
        return count;
    }
 vector < int > countBits(int num){
        vector < int > bits(num+1);
        for(int i=0;i<=num;i++){
            bits[i] = countOnes(i);
        }
        return bits;
 }

Giải pháp với dynamic programming:

• Độ phức tạp thời gian: O(n)
• Độ phức tạp không gian: O(n)

vector < int > countBits(int num){
        vector< int > bits(num+1);
        bits[0] = 0;
        for(int i=1;i<=num;i++){
            if(i&#038;1) bits[i]=bits[i-1]+1;
            else
                bits[i]=bits[i>>1];
        }
        return bits;
    }