338. Counting Bits

📝 Problem Details

• Title: 338. Counting Bits
• Link: https://leetcode.com/problems/counting-bits/
• Difficulty: Easy
• Tags/Categories: Bit-Manipulation

input integer n return vector<int> ans of length n+1 such that for each i, ans[i] is the number of 1s in the binary representation of 1

💡 Explanation of Solution

- for each number:
	- use bitwise operations to count how many bits are set

⌛ Complexity Analysis

Time Complexity: O(n * log n)
	each number requires up to log n bit checks

Space Complexity: O(n)

💻 Implementation of Solution

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ans;
 
        for(int i = 0; i <= n; i++) { // include n
            int count = 0;
            int num = i; // make a copy so we don’t modify the loop variable
            while(num > 0) {
                count += (num & 1);
                num >>= 1;
            }
            ans.push_back(count);
        }
 
        return ans;
    }
};