Binary Numbers

Easy

0/40

Average time to solve is 10m

Contributed by

24 upvotes

Asked in company

Problem statement

Given a number ‘N’, you are supposed to calculate the number of 1s in the binary representation of the given number.

For example:

Given ‘N’ = 4, 
Its binary representation is 0..0100, therefore there is only 1 set bit, hence the answer will be 1.

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

Input format:

The first line of input contains ‘T’, denoting the number of test cases. Then each test case follows.

Each test case contains a single integer ‘N’, denoting the number given.

Output Format :

For each test case, print a single line that contains a single integer that denotes the total number of 1s which satisfy the above description.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints:

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

Time Limit: 1 sec.

Sample Input 1 :

2
4
3

Sample Output 1 :

1
2

Explanation of the Sample Input 1:

For the first test case :  
The binary representation 4 is 0..0100, therefore there is only 1 set bit. Hence, the answer will be 1.

For the Second Test case:
The binary representation 3 is 0..0011, therefore there are 2 set bits. Hence, the answer will be 2.

Sample Input 2 :

2
16 
15

Sample Output 2 :

1
4

Hint 1

Hint 2

Can you check every bit of the given number?

Approaches (2)

Approach 1

Approach 2

Checking every bit

The idea is to check every bit in the number and maintain a counter and increase it by 1 if the bit is set.

The steps are as follows:

Maintain a variable ‘setBits,’ which is initially 0, which will store the count of set bits.
Execute a while loop with the condition that the number is greater than zero:
- If the current bit is set, increase ‘setBits’ by 1.
- We will right-shift the number by 1 place.
Return ‘setBits’ as the final answer.

Time Complexity

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

Since the max number of bits, a number can have is log(N). Hence, the overall time complexity will be O(log(N)).

Space Complexity

O(1).

Since we are not using any extra space. Hence, the overall space complexity is O(1).

(100% EXP penalty)

Binary Numbers

Console