Last Updated: 3 Dec, 2021
Bits Counting
Easy
Asked in companies
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.
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
Approaches
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.
- If (i & (1 << j)) != 0.
- Print ‘counter’.
Approach: We can see that every odd number has one more set bit than the number that is half of the current odd number. At the same time, every even number has the same set bit as the number that is half of the current even number.
Algorithm:
- Create an array ‘dp’ of length ‘N + 1’ and initialize its values to 0.
- Iterate using a for loop from i = ‘1’ to ‘N’.
- If ‘i’ is divisible by 2.
- Update dp[i] to dp[i >> 1].
- Else.
- Update dp[i] to dp[i >> 1] + 1.
- If ‘i’ is divisible by 2.
- Print all the values of ‘dp’.
Similar problems