338. Counting Bits: Leetcode Step-by-Step Approach

Counting Bits - LeetCode

Photo by Content Pixie on Unsplash

PROBLEM STATEMENT:

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.

APPROACH:

1. The ‘countBits’ function will take an integer n as input and return a vector containing the number of set bits for each integer from 0 to n. The function will utilize the bitwise AND operator (&) to efficiently count the set bits.

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ans(n + 1, 0);

        for (int i = 1; i <= n; i++) {
            ans[i] = 1 + ans[i & (i - 1)];
        }

        return ans;
    }
};

int main() {
    int n;
    cin >> n;

    Solution solution;
    vector<int> result = solution.countBits(n);

    for (int i = 0; i <= n; i++) {
        cout << result[i] << " ";
    }

    cout << endl;

    return 0;
}

TIME COMPLEXITY: O(N)

SPACE COMPLEXITY: O(N)