Count Set Bits
You are given a positive integer ‘N’. Your task is to find the total number of ‘1’ in the binary representation of all the numbers from 1 to N.

Since the count of ‘1’ can be huge, you are required to return it modulo 1e9+7.

Note:

Do not print anything, just return the number of set bits in the binary representation of all integers between 1 and ‘N’.

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the next ‘T’ lines represent the ‘T’ test cases. The first line of each test case contains a single integer ‘N’.

Output Format

For each test case, return an integer that is equal to the count of set bits in all integers from 1 to n modulo 1e9+7. Output for each test case will be printed in a new line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Count Set Bits

You are given a positive integer ‘N’. Your task is to find the total number of ‘1’ in the binary representation of all the numbers from 1 to N.

Since the count of ‘1’ can be huge, you are required to return it modulo 1e9+7.

Note:

Do not print anything, just return the number of set bits in the binary representation of all integers between 1 and ‘N’.

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases to run. 
Then the next ‘T’ lines represent the ‘T’ test cases.

The first line of each test case contains a single integer ‘N’.

Output Format

For each test case, return an integer that is equal to the count of set bits in all integers from 1 to n modulo 1e9+7.

Output for each test case will be printed in a new line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= N <= 10^9

Time limit: 1 second

Accepted Answer

The direct approach would be to loop through all bits in an integer, check if a bit is set and if it is, then increment the set bit count.
Time Complexity: Θ(logn) (Theta of logn)
Auxiliary Space: O(1)

Brian Kernighan’s Algorithm can also be used here.
This algorithm is based on the idea that subtracting 1 from a decimal number flips all the bits after the rightmost set bit(which is 1) including the rightmost set bit.
For example :
10 in binary is 00001010
9 in binary is 00001001
8 in binary is 00001000
So if we subtract a number by 1 and do it bitwise & with itself (n & (n-1)), we unset the rightmost set bit. If we do n & (n-1) in a loop and count the number of times the loop executes, we get the set bit count.
The number of times it loops is equal to the number of set bits in a given integer.

Algorithm :
1 Initialize count: = 0
2 If integer n is not zero
(a) Do bitwise & with (n-1) and assign the value back to n
n: = n&(n-1)
(b) Increment count by 1
(c) go to step 2
3 Else return count

Accepted Answer

Brute Force

The key idea is to count the number of set bits in each number from 1 to n and return the sum of all set bits.

The algorithm will be -

For each i from 1 to N -
- We find the number of set bits for each i.
- This can be done using a built-in function (for eg builtin_popcount in c++) or by simply using a loop and left shifting the number and finding if the last place is set or not.
Finally we store the count of set bits in a variable called ‘count’ , take its mod and return it.

Space Complexity: O(1)Explanation:

O(1)

Since we are using constant space.

Time Complexity: O(nlogn)Explanation:

O(N * log(N)), where ‘N’ is the given number.

For each number in 1 to N, it will take log(N) time to find the number of set bits in it. Hence the complexity is N * log(N).

Java (SE 1.8)

/*

    Time Complexity: O(N * log(N))

    Space Complexity: O(1)



    Where 'N' is the given number

*/



import java.util.*;

import java.lang.*;



public class Solution 

{



	public static int countSetBitsHelper(int n) 

	{

		int count = 0;



		while (n > 0) 

		{

            

			// Check if last bit is set

			if (n % 2 != 0) 

			{

				count += 1;

			}



			// Divide by 2

			n = n / 2;

		}



		return count;

	}



	public static int countSetBits(int n) 

	{

		int mod = (int)1e9 + 7;



		int count = 0;



		for (int i = 1; i <= n; i++) 

		{



			// For each number find it's contribution to the count

			count = (count + countSetBitsHelper(i)) % mod;

		}



		return count;



	}

}

Python (3.5)

'''

    Time Complexity: O(N * log(N))

    Space Complexity: O(1)



    Where 'N' is the given number

'''



def countSetBitsHelper(n):

    

    count = 0



    while (n):



        # Check if last bit is set

        if(n % 2 != 0):

        	count = count + 1



        # Divide by 2

        n >>= 1;

    

    return count



def countSetBits(n):



	mod=1000000007

	count = 0



	for i in range(n+1):



		# For each number find it's contribution to the count

		count = count + countSetBitsHelper(i)



	count %= mod

	

	return count

C++ (g++ 5.4)

/*

    Time Complexity: O(N * log(N))

    Space Complexity: O(1)



    Where 'N' is the given number

*/



int countSetBitsHelper(int n) {

    int count = 0;



    while (n) {



        // Check if last bit is set

        if(n % 2 != 0){



            count += 1;

        }



        // Divide by 2

        n >>= 1;

    }



    return count;

}



int countSetBits(int n) {



    int mod = (int)1e9 + 7;

    int count = 0;



    for (int i = 1; i <= n; i++) {

        

        // For each number find it's contribution to the count

        count = (count + countSetBitsHelper(i)) % mod;

    }



    return count;

}

Accepted Answer

Optimised approach

Let us take the following example:

Let N = 7;

Then ,

0 = 0000

1 = 0001

2 = 0010

3 = 0011

4 = 0100

5 = 0101

6= 0110

7 = 0111

Observe the last the bits get flipped after (2^0 = 1)

The second last bit gets flipped after( 2^1=2)

The third last bit gets flipped after (2^2=4)

We can use the above observation to get the result. The algorithm will be:

We add 1 to the given number to ensure correctness as the binary number system starts from 0. Thus, we increment n by 1.
We need to keep the count of set bits. Let us do that in a ‘count’ variable.
We initialize count with N / 2 as we know that there will be N / 2 odd numbers between 1 to N and the last bit of odd numbers is set.
Now, for each, i starting from 0, till 2 ^ i becomes greater than n we do-
- We will get the pairs of numbers of 1s and zeros ‘totalpairs’ for the current bit by dividing ‘N’ by 2 ^ i.
- Now, multiplying ‘totalpairs / 2’ with the current power of 2 will give us the number of 1s in that position. Thus we add, (‘totalpairs / 2’ * current power of 2) to count.
- If ‘totalpairs’ is odd we necessarily miss a few ones, so we add ‘N’ modulo current power of 2 to ‘count’.
Don't forget to take mod!.
Finally, we return count.

Space Complexity: O(1)Explanation:

O(1)

Since we are using constant space.

Time Complexity: O(logn)Explanation:

O(log(N)), where ‘N’ is the given number.

Since the while loop increments with the power of 2, the complexity will be in order of log(n)

C++ (g++ 5.4)

/*

    Time Complexity: O(log(N))

    Space Complexity: O(1)



    Where 'N' is the given number

*/



int countSetBits(int n) {



    int mod = (int)1e9 + 7;



    n++;



    // To store the powers of 2

    int powerOf2 = 2;



    

    int count = n / 2;



    // Loop for every bit required to represent n

    while (powerOf2 <= n) {

        

        int totalPairs = n / powerOf2;



        count = (count + ((totalPairs / 2) * powerOf2) % mod) % mod;



        /* 

            If the count of pairs was odd then

            add the remaining 1s which could

            not be groupped together 

        */



        if (totalPairs & 1) {

            count = (count + n % powerOf2) % mod;

        }



        // Next power of 2

        powerOf2 <<= 1;

    }

    count %= mod;



    return count;

}

Python (3.5)

'''

    Time Complexity: O(log(N))

    Space Complexity: O(1)



    Where 'N' is the given number

'''



def countSetBits(n):



	mod = 1000000007

	n = n + 1

	count = n // 2



	# To store the powers of 2

	powerOf2 = 2



	# Loop for every bit required to represent n

	while(powerOf2 <= n):



		totalPairs = n // powerOf2

		count = count + (totalPairs // 2) * powerOf2



		''' 

            If the count of pairs was odd then

            add the remaining one's which could

            not be grouped together 

        '''

		if(totalPairs % 2 != 0):

			count = count + n %  powerOf2



		# Next power of 2

		powerOf2 <<= 1



	count %= mod



	return count

Java (SE 1.8)

/*

    Time Complexity: O(log(N))

    Space Complexity: O(1)



    Where 'N' is the given number

*/



import java.util.*;

import java.lang.*;



public class Solution 

{



	public static int countSetBits(int n) 

	{

		int mod = (int)1e9 + 7;



		n++;



		// To store the powers of 2

		int powerOf2 = 2;



		int count = n / 2;



		// Loop for every bit required to represent n

		while (powerOf2 <= n) 

		{



			int totalPairs = n / powerOf2;



			count = (count + ((totalPairs / 2) * powerOf2) % mod) % mod;



			/*

			    If the count of pairs was odd then

			    add the remaining 1s which could

			    not be groupped together

			*/



			if ((totalPairs & 1) > 0) 

			{

				count = (count + n % powerOf2) % mod;

			}



			// Next power of 2

			powerOf2 = powerOf2 * 2;

		}

		count = count % mod;



		return count;



	}

}

You are given a positive integer ‘N’. Your task is to find the total number of ‘1’ in the binary representation of all the numbers from 1 to N.

Since the count of ‘1’ can be huge, you are required to return it modulo 1e9+7.

Note:

Input Format:

Output Format

Note:

Constraints:

Top One Convergence Software Developer interview questions & answers

Popular interview questions of Software Developer