Back to solutions

Counting Bits

EasyBit Manipulation

Return an array where the i-th element is the number of set bits in i, for all i from 0 to n.

Open problem
Constraints
  • 0 <= n <= 10^5

DP on lowest bit removed

Time O(n)Space O(n)

bits[i] equals bits[i >> 1] plus the last bit (i & 1), because dropping the lowest bit gives a previously computed smaller number.

#include <bits/stdc++.h>
using namespace std;

vector<int> countBits(int n) {
    vector<int> bits(n + 1, 0);
    for (int i = 1; i <= n; i++) bits[i] = bits[i >> 1] + (i & 1);
    return bits;
}