Counting Bits - Tutorial

Problem statement : Given an integer n, return an array ans whose length is n+1 such that for each i (0 <= i <= n) ans[i] is the number of 1’s in binary representation of i.

Example:

Input:  n = 5
Output: [0, 1, 1, 2, 1, 2 ]

Explanation:

Solution:

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1: Counting no of set bits in each number from 0 to n

Approach:

Count the no of set bits in each number from 0 to n and store the set bits count for each number in the array and return the array.

Code :

C++ Code

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

vector<int> countingSetBits(int n)
{
    vector<int> ans(n + 1);
    for (int i = 0; i <= n; i++)
    {
        int num = i, cnt = 0;
        while (num > 0)
        {
            if (num & 1)
                cnt++;
            num = num >> 1;
        }
        ans[i] = cnt;
    }
    return ans;
}
int main()
{
    int n=5;
    vector<int> ans = countingSetBits(n);
    for (auto &val : ans)
        cout << val << " ";
    return 0;
}

Output: 0 1 1 2 1 2

Time Complexity: O( Nlog(N) ), We are iterating from 0 to n, which takes O(N) time and in each iteration, we are finding the no of set bits in binary representation, which takes O(logN).So overall time complexity is O(NlogN)

Space Complexity: O(N) space for the ans vector.

Java Code

import java.util.*;

class TUF{
static int[] countingSetBits(int n)
{
    int ans[]=new int[n + 1];
    for (int i = 0; i <= n; i++)
    {
        int num = i, cnt = 0;
        while (num > 0)
        {
            if ((num & 1)==1)
                cnt++;
            num = num >> 1;
        }
        ans[i] = cnt;
    }
    return ans;
}
public static void main(String args[])
{
    int n=5;
    int ans[] = countingSetBits(n);
    for (int val : ans)
    System.out.print(val+" ");
}
}

Output: 0 1 1 2 1 2

Time Complexity: O( Nlog(N) ), We are iterating from 0 to n, which takes O(N) time, and with each iteration, we are finding the no of set bits in binary representation, which takes O(logN). So overall time complexity is O(NlogN)

Space Complexity: O(N) space for the ans vector.

Python Code

n = 5

def countingSetBits(n):
    ans = []
    for i in range(0, n+1):
        num = i
        cnt = 0
        while num > 0:
            if num & 1:
                cnt += 1
            num = num >> 1
        ans.append(cnt)
    return ans

ans = countingSetBits(n)
print(ans)

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

Space Complexity: O(N) space for the ans vector.

Solution 2 :

Observation :

Suppose we have two numbers X and Y such that X/2 = Y, then

Example:

Let X = 7, So Y = X/2 = 7/2 = 3
7 → 111 → 3
3 → 011 → 2

No of setbits in X - No of setbits in Y = 3 - 2 = 1

Proof of Observation :

The X can be odd or even.

Case 1: X is odd

If X is odd then the last bit or Least Significant Bit of the X would be set. Dividing by 2 means left shifting the bits 1 time, If we left shift the bits, the Least Significant Bit is Lost. That is one set bit is lost in the X. We know that X/2 is nothing but Y, so the Y has one less set bit than X.

Case 2: X is even

If X is even then the last bit or Least Significant Bit of the X would be unset. Upon the left shift of the bits, the Least Significant Bit is Lost. That is one unset bit is lost in the X. So No of the set bits remained unchanged even after dividing by 2.

In both Cases combined we can say

So if we know the no of set bits in X/2 then no of set bits in X is

If X is odd

No of Set Bits in X = No of Set Bits in X/2 +1

If X is even

No of Set Bits in X = No of Set Bits in X/2

We can use this observation to find the set bits in each number from 0 to n in O(N) time.

Approach :

Let ans be array of size n where ans[i] is the no of setbits in i ( 0 <= i<= n)

We know that no of set bits in 0 is 0, and set bits in 1 is 1

So ans[0] = 0, ans[1] = 1

Let n be 5, Now iterate over 2 to n and find out the set bits in each number.

X	Parity of X	X/2	Set Bits in X/2	Set Bits in X
2	Even	1	ans[1] = 1	ans[X] = ans[X/2] ans[2] = ans[1] = 1
3	Odd	1	ans[1] = 1	ans[X] = ans[X/2] + 1 ans[3] = ans[1] + 1 = 1+1 = 2
4	Even	2	ans[2] = 1	ans[X] =ans[X/2] ans[4] = ans[2] = 1 = 1
5	Odd	2	ans[2] = 1	ans[X] = ans[X/2] + 1 ans[5] = ans[2] + 1 = 1 + 1 = 2

Code:

C++ Code

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

vector<int> countingSetBits(int n)
{
    vector<int> ans(n + 1);
    if (n == 0)
        return {0};
    if (n == 1)
        return {0, 1};
    ans[0] = 0, ans[1] = 1;
    for (int i = 2; i <= n; i++)
        ans[i] = i & 1 ? ans[i / 2] + 1 : ans[i / 2];
    return ans;
}
int main()
{
    int n=5;
    vector<int> ans = countingSetBits(n);
    for (auto &val : ans)
        cout << val << " ";
    return 0;
}

Output: 0 1 1 2 1 2

Time Complexity: O(n)

Space Complexity: O(n)

Java Code

import java.util.*;

class TUF{
static int[] countingSetBits(int n)
{
    int ans[]=new int[n + 1];
    if (n == 0)
        return new int[]{0};
    if (n == 1)
        return new int[]{0,1};
    ans[0] = 0;
    ans[1] = 1;
    for (int i = 2; i <= n; i++)
        ans[i] = (i & 1)==1 ? ans[i / 2] + 1 : ans[i / 2];
    return ans;
}
public static void main(String args[])
{
    int n=5;
    int ans[] = countingSetBits(n);
    for (int val : ans)
    System.out.print(val+" ");
}
}

Output: 0 1 1 2 1 2

Time Complexity: O(n)

Space Complexity: O(n)

Python Code

n = 5

def countingSetBits(n):
    ans = [0]*(n+1)
    if n == 0:
        return [0]
    if n == 1:
        return [0, 1]
    ans[0] = 0
    ans[1] = 1
    for i in range(0, n+1):
        if i & 1:
            ans[i] = ans[i//2] + 1
        else:
            ans[i] = ans[i//2]
    return ans


ans = countingSetBits(n)
print(ans)

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

Time Complexity: O(n)

Space Complexity: O(n)

Special thanks to SaiSri Angajala for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article. If you want to suggest any improvement/correction in this article please mail us at [email protected]