Set Bits

Easy

0/40

Contributed by

284 upvotes

Asked in companies

Problem statement

Write a program to count the number of 1's in the binary representation of an integer.

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

Input format :

 The only line of input contains a single integer N.

Output format :

The only line of the output prints the total number of 1.

Constraints

1 <= N <= 100

Sample Input 1:

Sample Output 1:

Explanation of Sample Input 1:

Binary Representation of 9 is 1001.

Sample Input 2:

Sample Output 2:

Hint 1

Iterate through all bits

Approaches (1)

Approach 1

Looping through bits Approach

Here we are converting the number into binary, and during the conversion, we are checking the remainder part.
If it is 1, then we increment the value of count by 1.

Time Complexity

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

Since we are iterating through each bit of binary representation of the given number which is O(log(N)) in size. So the overall time complexity will be O(log(N)).

Space Complexity

O(1)

We are using constant extra space.

(100% EXP penalty)

Set Bits

Console