# Challenge 1: Count Set Bits Or Number of 1 bit's

This is a traditional problem counting the number of set bits or 1's present in a number. Let’s see how we can count the set bits using the AND operator.

This is a traditional problem counting the number of set bits or 1's present in a number.

## Introduction

Let’s see how we can count the set bits using the AND operator.

1 = set-bit
0 = unset-bit

## Example:

``````Input: 5

Output: 0101 (in binary)``````

There are two set bits are two in the above example, as we have two 1s in the binary representation.

## Problem statement

Write a program to count set bits of an integer.

``````Input: 125

Output: 6 ``````

Explanation: Input has six 1’s or set-bits so the output will be 6.

## Intuition

In this program, a while-loop is iterated until the expression `number > 0` is evaluated to `0` (false).

Let’s see the iterations for `number = 125`.

### Iterations

• After the first iteration,` number(125)` will be divided by `2`, its value will be `62`, and the count incremented to `1`.
• After the second iteration, the value of `number(62)` will be `31` and the count incremented to `2`.
• After the third iteration, the value of `number(31)` will be `15`, and the count incremented to `3`.
• And so on.

Then the expression is evaluated as false since the `number` is `0`, and the loop terminates.

### Iteration table

number number = (number/2) set/unset (1/0) setbit count
125 62 1 1
62 31 0 1
31 15 1 2
15 7 1 3
7 3 1 4
3 1 1 5
1 0 1 6

## Solutions

You will see the Java solution, which is then refactored for better readability.

### Java

``````class CountSetBit {
private static int helper(int n) {
int ans = 0;
while (n > 0) {
if (n % 2 != 0) {
ans++;
}
n /= 2;
}
return ans;
}

public static void main(String[] args) {
int number = 125;
System.out.println("SetBit Count is : " + helper(number));
}
}``````

We can further rewrite this code using the `&` operator as seen below.

``````public class CountSetBit {
private static int helper(int n) {
int count = 0;
while (n > 0) {
if ((n & 1) == 1) {
count++;
}
n >>= 1;
}
return count;
}

public static void main(String[] args) {
int number = 125;
System.out.println("SetBit Count is : " + helper(number));
}
}``````

This can be further simplified as shown below:

``````public class CountSetBit {
private static int helper(int n) {
int count = 0;
while (n > 0) {
count += (n & 1);
n >>= 1;
}
return count;
}

public static void main(String[] args) {
int number = 125;
System.out.println("SetBit Count is : " + helper(number));
}
}``````

### Python

You will see the Python solution, which is then refactored for better readability.

``````def helper(n):
ans = 0
while n > 0:
if n % 2 != 0:
ans += 1
n //= 2
return ans

number = 125
print("SetBit Count is : ", helper(number))
``````

We can further rewrite this code using the `&` operator as seen below.

``````def helper(n):
count=0
while n > 0:
if ((n & 1) == 1):
count+=1
n >>= 1
return count

number=125
print("SetBit Count is : ",helper(number))``````

This can be further simplified as shown below:

``````def helper(n):
count=0
while n > 0:
count+=(n & 1)
n >>= 1

return count

number=125
print("SetBit Count is : ",helper(number))``````

### JavaScript

You will see the JavaScript solution, which is then refactored for better readability.

``````const CountSetBits = (n) => {
let count = 0;
while (n > 0) {
if(n % 2 !== 0) {
count++;
}
n >>= 1;
}

return count;
}

console.log ('SetBit Count is', CountSetBits (125));
``````

We can further rewrite this code using the `&` operator as seen below.

``````const CountSetBits = (n) => {
let count = 0;
while (n > 0) {
if ((n & 1) === 1) {
count++;
}
n >>= 1
}

return count;
}

console.log ('SetBit Count is', CountSetBits (125));
``````

This can be further simplified as shown below:

``````const CountSetBits = (n) => {
let count = 0;
while (n > 0) {
count += (n & 1);
n >>= 1;
}

return count;
}

console.log ('SetBit Count is', CountSetBits (125));
``````

### C++

You will see the C++ solution, which is then refactored for better readability.

``````#include <iostream>
using namespace std;

int helper(int n){
int count = 0;

while (n > 0){
if (n % 2 != 0){
count++;
}
n /= 2;
}

return count;
}

int main() {
int number = 125;
cout << "SetBit count is : " << helper(number);
return 0;
}``````

We can further rewrite this code using the `&` operator as seen below.

``````#include <iostream>
using namespace std;

int helper(int n) {
int count = 0;
while (n > 0) {
if ((n & 1) == 1) {
count++;
}
n >>= 1;
}
return count;
}

int main() {
int number = 125;
cout << "SetBit count is : " << helper(number);
}``````

This can be further simplified as shown below:

``````#include <iostream>
using namespace std;

int helper(int n) {
int count = 0;

while (n > 0) {
count += (n & 1);
n >>= 1;
}
return count;
}

int main() {
int number = 125;
cout << "SetBit count is : " << helper(number);
return 0;
}``````

### TypeScript

You will see the TypeScript solution, which is then refactored for better readability.

``````export const CountSetBits = (n: number): number => {
let count: number = 0;
while (n > 0) {
if (n % 2 !== 0) {
count++;
}
n >>= 1;
}
return count;
}

console.log('SetBit Count is', CountSetBits(125));``````

We can further rewrite this code using the `&` operator as seen below.

``````export const CountSetBits = (n: number): number => {
let count: number = 0;
while (n > 0) {
if ((n & 1) === 1) {
count++;
}
n >>= 1
}

return count;
}

console.log('SetBit Count is', CountSetBits(125));
``````

This can be further simplified as shown below:

``````export const CountSetBits = (n: number): number => {
let count: number = 0;
while (n > 0) {
count += (n & 1);
n >>= 1;
}

return count;
}

console.log('SetBit Count is', CountSetBits(125));``````

## Time and space complexities

### Time complexity: O(Total bits in n) / O(1) in simple terms

The time taken is proportional to the total bits in binary representation, which means

`int` takes `32` bits => `O(32 bits)` time.
`long` takes `64` bits => `O(64 bits)` time.

So, the time taken is O(Total bits in `n`, which can be an int or long, etc.).

The run time depends on the number of bits in n. In the worst case, all bits in n are 1-bits. In the case of a 32-bit integer, the run time is `O(32)` or `O(1)`.

### Space complexity: O(1) extra space

The space complexity is `O(1)`. No extra space is allocated.

## Coding exercise

Now, try to optimize the above snippets. There is a better way to solve this problem.

This problem is designed for your practice, so try to solve it yourself first. If you get stuck, you can always refer to the solution in the next lesson. Good luck!

Hint: Learn about "Brian Kernighan’s algorithm", because in next solution review, we are about to solve this with his approach.
``````// java
// TODO: finish the challenge or check next lesson for solution
class Solution{
public static int countSetBits(int n){
// Write - Your - Code- Here

return -1; // change this and return the correct setbit count
}
}``````
``````# python
# TODO: finish the challenge or check next lesson for solution
def Solution(n):
# Write - Your - Code- Here

return -1 # change this and return the correct setbit count``````
``````// javascript
// TODO: finish the challenge or check next lesson for solution
const CountSetBits = (number) => {
// Write - Your - Code- Here

return -1; // change this and return the correct setbit count
}``````
``````// c++
// TODO: finish the challenge or check next lesson for solution
#include <iostream>
using namespace std;

int countSetBits(int n) {
// Write - Your - Code- Here

return -1; // change this and return the correct setbit count
}``````
``````// typescript
// TODO: finish the challenge or check next lesson for solution
export const CountSetBits = (n: number): number => {
// Write - Your - Code- Here

return -1; // change this and return the correct setbit count
}``````

The solution will be explained in the next lesson.

Coding Interview QuestionsData Structures and AlgorithmsBit Manipulation

Gopi is an engineering leader with 12+ of experience in full-stack development—a specialist in Java technology stack. He worked for multiple startups, the European govt, and FAANG in India and Europe.

Members Public

## Leetcode 217: Contains Duplicate

This question marks the first problem when working on duplicate data, either integers or strings etc. Companies that have asked this in their coding interview are Amazon, Apple, Netflix, Google, Microsoft, Adobe, Facebook, and many more top tech companies. Problem statement Given an integer array nums, return true if any

Members Public

## Leetcode 121: Best Time To Buy and Sell Stock

The Best time to buy and sell stock problem is a classic problem that can be solved using the Greedy approach. This is one of the most popular questions asked in such interviews. Companies that have asked this in their coding interview are Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe,

Members Public

## Bit Manipulation Course Overview

Overview In this course, you will learn how to solve problems using bit manipulation, a powerful technique that can be used to optimize your algorithmic and problem-solving skills. This is one of the most important/critical topics when someone starts preparing for coding interviews for FAANG companies. To kick things