338. Counting Bits

Problem

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

Solution

Iterative - O(n log n) time - O(n) space

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ans;
        for(int i = 0; i <= n; i++) {
			int sum = 0;
            int num = i;
            while(num != 0) {
                sum += num%2;
                num = num/2;
            }
			ans.push_back(sum);
        }
        return ans;
    }
};

Iterative - O(n) time - O(n) space

This makes use of Binary Conversion

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> results;
        results.push_back(0);
        for (int i = 1; i <= n; i++) {
            results.push_back(results[i/2] + i%2);
        }
        return results;
    }
};

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ans(n + 1, 0);
        for(int i = 1; i <= n; i++) {
           if (i % 2 == 0) ans[i] = ans[i/2];
           else ans[i] = ans[i-1] + 1;
           return ans;
		}
    }
};

Recursion - O(n²) time - O(n) space

class Solution {
public:
    int bitNumber(int n) {
        if (n == 0) return 0;
        
        if (n % 2 == 0) {
            double power = log2(n);
            if (floor(power) == ceil(power)) return 1;
            int newNumber = pow(2, floor(power)); 
            return bitNumber(newNumber) + bitNumber(n - newNumber);
        }
        else return 1 + bitNumber(n - 1);
    }
 
    vector<int> countBits(int n) {
        vector<int> result;
        for (int i = 0; i <= n; i++) {
            result.push_back(bitNumber(i));
        }
        return result;
    }
};

Dynamic Programming Top-Down - O(n²) time - O(n) space

class Solution {
public:
    vector<int> results;
    int bitNumber(int n) {
        if (n == 0) return 0;
        if (n % 2 == 0) {
            double power = log2(n);
            if (floor(power) == ceil(power)) return 1;
            int newNumber = pow(2, floor(power));
            return 1 + (results[n-newNumber] ? results[n-newNumber] : bitNumber(n - newNumber));
        }
        else return 1 + (results[n-1] ? results[n-1] : bitNumber(n-1));
    }
 
    vector<int> countBits(int n) {
        for (int i = 0; i <= n; i++) {
            results.push_back(bitNumber(i));
        }
        return results;
    }
};