Day 28 : LeetCode 30 Day May Challenges

counting_bits.cpp

class Solution {
public:
    //sizeof(int) = 32 bits/4 bytes
    //what i observed is
    //0 1  2 3   4 5 6 7   8 9 10 11 12 13 14 15  16 ... indices
    //0 1 [1 2][1 2, 2 3] [1 2  2  3, 2  3  3  4] [1 2 2 3 2 3 3 4, 2 3 3 4 3 4 4 5]
    vector<int> countBits(int num) {
        if(num == 0)
            return {0};
        else if(num == 1)
            return {0,1};
        else if(num == 2)
            return {0,1,1};
        else if(num == 3)
            return {0,1,1,2};
        else {
            vector<int> v(num+1,0);
            v[0] = 0;v[1] = 1;v[2] = 1; v[3] = 2;
            //num >= 4
            int l = 4;
            while(true){
                if(l == num+1)
                    break;
                int n = l/2;
                for(int i=1; i<=n && l<=num; i++){
                    v[l] = v[l-n];
                    l++;
                }
                for(int i=n+1; i<=2*n && l<=num; i++){
                    v[l] = v[l-n]+1;
                    l++;//l -> 8,16,.....
                }
            }
            return v;
        }
    }
};
//BELOW TWO SOLUTIONS ARE WITHOUT ANY HINTS SEEN
    //sizeof(int) = 32 bits/4 bytes
    /*
    vector<int> countBits(int num) {
        int l=2;
        vector<int> v(num+1,0);
        int prev_count;
        for(int i=0; i<=num; i++){
            int count = 0;
            if(i == l){
                //for every powers of 2,set to 1
                v[i] = 1;
                l*=2;
                prev_count = 1;
            }
            else if((i-1)%2 == 0){
                v[i] = prev_count+1;
            }
            else{
                for(int j=0; j<32; j++){
                    if(i&(1<<j))
                        count++;
                }
                v[i] = count;
                prev_count = count;
            }
        }
        return v;
    }
*/
/*
vector<int> v;
        for(int i=0; i<=num; i++){
            int count = 0;
            for(int j=0; j<32; j++){
                if(i&(1<<j))
                    count++;
            }
            v.push_back(count);
        }
        return v;
*/

problem_statement28.txt

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.

Example 1:

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

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

It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
Space complexity should be O(n).
Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.
   Hide Hint #1  
You should make use of what you have produced already.
   Hide Hint #2  
Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous.
   Hide Hint #3  
Or does the odd/even status of the number help you in calculating the number of 1s?