Data Structures & Algorithms in Java – Binary – Counting Bits

Problem:

Given an integer , find the number of 1 bits for every number (in binary form) starting from 0 to that integer.

Input:

8

Output:

[0,1,1,2,1,2,2,3,1]

For the number 8 , you need to find the number of 1 bits in the numbers 0,1,2,3,4,5,6,7,8 and store them in an output array in their respective index.

Try out the solution here:

https://leetcode.com/problems/counting-bits/

Solution:

The below post explains how to find the number of 1 bits in a single integer :

The time complexity for the above algorithm(the optimal one) is O(logn).

If you use the above algorithm for each number upto the given integer input n , then it will take O(nlogn) time .

A better solution exists which takes only O(n) time complexity.

Hint:

• When you divide a number by 2, it gets right shifted by 1 place and you loose the rightmost bit

Optimal Solution:

Let’s analyze the above hint:

If you divide a number by 2, it gets right shifted by 1 digit.

So if it is an even number , the last digit will be 0 , so the number of “1 bits” remain the same even after the division.

So ,

Number of 1 bits in a even number = Number of 1 bits in the even number divided by 2.

If it is an odd number , the last digit will be 1 , so on right shifting (dividing by 2) you loose the last “1 bit”. Hence the number of 1 bits in an odd number is one less than the number of 1 bits in an odd number divided by 2.

So,

Number of 1 bits in a odd number = Number of 1 bits in the odd number divided by 2 + 1.

Using these two concepts , you can write an algorithm which finds the solution in a single pass (O(n) time).

Here is the algorithm:

ALGORITHM:

STEP1: Initialize the first element of the output array to 0 (as the number of 1 bits in the element 0 is 0)

STEP2: For each element i from number 1 to the given integer n , find the number of 1 bits using the formula:

output[i] = output[i/2] for even numbers

output[i] = output[i/2] + 1 for odd numbers.

This can be represented in a single formula using :

output[i] = output[i/2] + (i%2)

i%2 will return 0 for even numbers and 1 for odd numbers.

STEP3: Return the output

Code:

class Solution {
    public int[] countBits(int n) {
        
        
        int[] output = new int[n+1];
     
        output[0] = 0;
        for(int i =1;i<=n;i++){
            
            output[i]=output[i/2]+i%2;
            
        }
        
        return output;
    }
}

The time complexity of above code is O(n) since we iterate through the for loop upto n times.

Space complexity is O(n) for the output array.