Bits Counting

Easy

0/40

Average time to solve is 25m

Contributed by

6 upvotes

Asked in companies

Problem statement

Ninja was given an integer ‘N’. For each number from ‘0’ to ‘N’, he must print the number of set bits present in its binary representation.

For example:

The binary representation of ‘5’ is 101. Therefore the number of set bits is 2.

Detailed explanation ( Input/output format, Notes, Images )

Input Format-

First-line contains ‘T’, denoting the number of Test cases.
For each Test case:
The first line contains an integer, ‘N’, denoting the number until you have to print the number of set bits in its binary representation.

Output Format-

For each test case, you have to print ‘N + 1’ space-separated integers, denoting the number of set bits in the binary representation.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints -

1 <= ‘T’ <= 10
0 <= ‘N’ <= 10^5 
Note- Sum of ‘N’ over all test cases does not exceed 10^5.

Time Limit: 1 sec

Sample Input-1

2
3
5

Sample Output-1

0 1 1 2
0 1 1 2 1 2

Explanation for Sample Input 1:

For test case 1:
    The binary representation of 0 is ‘0’. Hence the total set bit is 0.
    The binary representation of 1 is ‘1’. Hence the total set bit is 1.
    The binary representation of 2 is ‘10’. Hence the total set bit is 1.
    The binary representation of 3 is ‘11’. Hence the total set bit is 2.

Sample Input -2

 2
 0
 2

Sample Output -2

0
0 1 1

Hint 1

Hint 2

Check every bit of each number.

Approaches (2)

Approach 1

Approach 2

Brute Force

Approach: For each number, we will check all its bits. If the bit is set, we increase the counter. Else, check the next bit.

Algorithm:

Create a variable ‘counter’ and initialize it to ‘0’.
Iterate using a for loop from i = ‘0’ to ‘N’.
- Set ‘counter’ to ‘0’.
- Iterate using a for loop from j = ‘0’ to ‘17’.
  - If (i & (1 << j)) != 0.
    - Increment ‘counter’ by 1.
- Print ‘counter’.

Time Complexity

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

For each number, we are checking all its bits. Hence the overall complexity is O(N * log(N)).

Space Complexity

O(1).

We are creating a single variable. Hence the overall complexity is O(1).

(100% EXP penalty)

Bits Counting

Console