Count set bits in an integer

2.6
Write an efficient program to count number of 1s in binary representation of an integer.
Examples
Input : n = 6
Output : 2
Binary representation of 6 is 110 and has 2 set bits

Input : n = 13
Output : 3
Binary representation of 11 is 1101 and has 3 set bits

Recommended: Please solve it on “PRACTICE ” first, before moving on

to the solution.
1. Simple Method Loop through all bits in an integer, check if a bit is set and if it is then increment the
set bit count. See below program.
#include <stdio.h>

/* Function to get no of set bits in binary

representation of positive integer n */
unsigned int countSetBits(unsigned int n)
{
unsigned int count = 0;
while (n)
{
count += n & 1;
n >>= 1;
}
return count;
}
/* Program to test function countSetBits */
int main()
{
int i = 9;
printf("%d", countSetBits(i));
return 0;
}
Run on IDE
Time Complexity: (-)(logn) (Theta of logn)
2. Brian Kernighan’s Algorithm:
Subtraction of 1 from a number toggles all the bits (from right to left) till the rightmost set bit(including the
righmost set bit). So if we subtract a number by 1 and do bitwise & with itself (n & (n-1)), we unset the
righmost set bit. If we do n & (n-1) in a loop and count the no of times loop executes we get the set bit
count.
Beauty of the this solution is number of times it loops is equal to the number of set bits in a given integer.

1 Initialize count: = 0
2 If integer n is not zero
(a) Do bitwise & with (n-1) and assign the value back to n
n: = n&(n-1)
(b) Increment count by 1
(c) go to step 2
3 Else return count

Implementation of Brian Kernighan’s Algorithm:

#include<stdio.h>

/* Function to get no of set bits in binary

representation of passed binary no. */
unsigned int countSetBits(int n)
{
unsigned int count = 0;
while (n)
{
n &= (n-1) ;
count++;
}
return count;
}

/* Program to test function countSetBits */

int main()
{
int i = 9;
printf("%d", countSetBits(i));
getchar();
return 0;
}
Run on IDE
Example for Brian Kernighan’s Algorithm:
n = 9 (1001)
count = 0
 Since 9 > 0, subtract by 1 and do bitwise & with (9-1)
n = 9&8 (1001 & 1000)
n = 8
count = 1

Since 8 > 0, subtract

by 1 and do bitwise &
with (8-1)
n = 8&7 (1000 & 0111)
n = 0
count = 2

Since n = 0, return
count which is 2 now.
Time
Complexity: O(logn)
3. Using Lookup
table: We can count bits in
O(1) time using lookup
table. Please
seehttp://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable for details.
We can find one use of counting set bits at http://www.geeksforgeeks.org/?p=1465
Note: In GCC, we can directly count set bits using __builtin_popcount(). So we can avoid a separate
function for counting set bits.
// C++ program to demonstrate __builtin_popcount()
#include <iostream>
using namespace std;

int main()
{
cout << __builtin_popcount (4) << endl;
cout << __builtin_popcount (15);

return 0;
}
Run on IDE
Output :
1
4
Check if a given array can represent Preorder Traversal of Binary Search Tree
3.9
Given an array of numbers, return true if given array can represent preorder traversal of a Binary Search
Tree, else return false. Expected time complexity is O(n).
Examples:
Input: pre[] = {2, 4, 3}
Output: true
Given array can represent preorder traversal
of below tree
2

4
/
3

Input: pre[] = {2, 4, 1}

Output: false
Given array cannot represent preorder traversal
of a Binary Search Tree.

Input: pre[] = {40, 30, 35, 80, 100}

Output: true
Given array can represent preorder traversal
of below tree
40
/
30 80

35 100

Input: pre[] = {40, 30, 35, 20, 80, 100}

Output: false
Given array cannot represent preorder traversal
of a Binary Search Tree.
Recommended: Please solve it on “PRACTICE ” first, before moving on
to the solution.
A Simple Solution is to do following for every node pre[i] starting from first one.
1) Find the first greater value on right side of current node.
Let the index of this node be j. Return true if following
conditions hold. Else return false
(i) All values after the above found greater value are
greater than current node.
(ii) Recursive calls for the subarrays pre[i+1..j-1] and
pre[j+1..n-1] also return true.
Time Complexity of the above solution is O(n2)
An Efficient Solution can solve this problem in O(n) time. The idea is to use a stack. This problem is
similar to Next (or closest) Greater Element problem. Here we find next greater element and after finding
next greater, if we find a smaller element, then return false.
1) Create an empty stack.
2) Initialize root as INT_MIN.
3) Do following for every element pre[i]
a) If pre[i] is smaller than current root, return false.
b) Keep removing elements from stack while pre[i] is greater
then stack top. Make the last removed item as new root (to
be compared next).
At this point, pre[i] is greater than the removed root
(That is why if we see a smaller element in step a), we
return false)
c) push pre[i] to stack (All elements in stack are in decreasing
order)
Below is implementation of above idea.
C++
Java
Python
C++
// C++ program for an efficient solution to check if
// a given array can represent Preorder traversal of
// a Binary Search Tree
#include<bits/stdc++.h>
using namespace std;

bool canRepresentBST(int pre[], int n)

{
// Create an empty stack
stack<int> s;

// Initialize current root as minimum possible

// value
int root = INT_MIN;

// Traverse given array

for (int i=0; i<n; i++)
{
// If we find a node who is on right side
// and smaller than root, return false
if (pre[i] < root)
return false;

// If pre[i] is in right subtree of stack top,

// Keep removing items smaller than pre[i]
// and make the last removed item as new
// root.
while (!s.empty() && s.top()<pre[i])
{
root = s.top();
s.pop();
}

// At this point either stack is empty or

 // pre[i] is smaller than root, push pre[i]
s.push(pre[i]);
}
return true;
}

// Driver program
int main()
{
int pre1[] = {40, 30, 35, 80, 100};
int n = sizeof(pre1)/sizeof(pre1[0]);
canRepresentBST(pre1, n)? cout << "truen":
cout << "falsen";

int pre2[] = {40, 30, 35, 20, 80, 100};

n = sizeof(pre2)/sizeof(pre2[0]);
canRepresentBST(pre2, n)? cout << "truen":
cout << "falsen";

return 0;
}

Run on IDE
Java
// Java program for an efficient solution to check if
// a given array can represent Preorder traversal of
// a Binary Search Tree
import java.util.Stack;

class BinarySearchTree {

boolean canRepresentBST(int pre[], int n) {

// Create an empty stack
Stack<Integer> s = new Stack<Integer>();

// Initialize current root as minimum possible

// value
int root = Integer.MIN_VALUE;

// Traverse given array

for (int i = 0; i < n; i++) {
// If we find a node who is on right side
// and smaller than root, return false
if (pre[i] < root) {
return false;
}

// If pre[i] is in right subtree of stack top,

// Keep removing items smaller than pre[i]
// and make the last removed item as new
// root.
while (!s.empty() && s.peek() < pre[i]) {
root = s.peek();
s.pop();
}
 // At this point either stack is empty or
// pre[i] is smaller than root, push pre[i]
s.push(pre[i]);
}
return true;
}

public static void main(String args[]) {

BinarySearchTree bst = new BinarySearchTree();
int[] pre1 = new int[]{40, 30, 35, 80, 100};
int n = pre1.length;
if (bst.canRepresentBST(pre1, n) == true) {
System.out.println("true");
} else {
System.out.println("false");
}
int[] pre2 = new int[]{40, 30, 35, 20, 80, 100};
int n1 = pre2.length;
if (bst.canRepresentBST(pre2, n) == true) {
System.out.println("true");
} else {
System.out.println("false");
}
}
}

//This code is contributed by Mayank Jaiswal

Python
# Python program for an efficient solution to check if
# a given array can represent Preorder traversal of
# a Binary Search Tree

INT_MIN = -2**32

def canRepresentBST(pre):

# Create an empty stack

s = []

# Initialize current root as minimum possible value

root = INT_MIN

# Traverse given array

for value in pre:
#NOTE:value is equal to pre[i] according to the
#given algo

# If we find a node who is on the right side

# and smaller than root, return False
if value < root :
return False

# If value(pre[i]) is in right subtree of stack top,

 # Keep removing items smaller than value
# and make the last removed items as new root
while(len(s) > 0 and s[-1] < value) :
root = s.pop()

# At this point either stack is empty or value

# is smaller than root, push value
s.append(value)

return True

# Driver Program
pre1 = [40 , 30 , 35 , 80 , 100]
print "true" if canRepresentBST(pre1) == True else "false"
pre2 = [40 , 30 , 35 , 20 , 80 , 100]
print "true" if canRepresentBST(pre2) == True else "false"

# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

Output:
true
false

Program for Binary To Decimal Conversion

2
Given a binary number as input, we need to write a program to convert the given binary number into
equivalent decimal number.
Examples:
Input : 111
Output : 7

Input : 1010
Output : 10

Input: 100001
Output: 33
Recommended: Please solve it on “PRACTICE ” first, before moving on
to the solution.
The idea is to extract the digits of given binary number starting from right most digit and keep a variable
dec_value. At the time of extracting digits from the binary number, multiply the digit with the proper base
(Power of 2) and add it to the variable dec_value. At the end, the variable dec_value will store the
required decimal number.
For Example:
If the binary number is 111.
dec_value = 1*(2^2) + 1*(2^1) + 1*(2^0) = 7
Below diagram explains how to convert ( 1010 ) to equivalent decimal value:

Below is the C++ implementation of above idea.

// C++ program to convert binary to decimal
#include<iostream>
using namespace std;

// Function to convert binary to decimal

int binaryToDecimal(int n)
{
int num = n;
int dec_value = 0;

// Initializing base value to 1, i.e 2^0

int base = 1;

int temp = num;

while(temp)
{
int last_digit = temp % 10;
temp = temp/10;
 dec_value += last_digit*base;

base = base*2;
}

return dec_value;
}

// Driver program to test above function

int main()
{
int num = 10101001;

cout<<binaryToDecimal(num)<<endl;
}

Run on IDE
Output:
169
Note: The program works only with binary numbers in the range of integers. In case you want to work
with long binary numbers like 20 bits or 30 bit, you can use string variable to store the binary numbers.
Below is a similar program which uses string variable instead of integers to store binary value:
// C++ program to convert binary to decimal
// when input is represented as binary string.
#include<iostream>
#include<string>
using namespace std;

// Function to convert binary to decimal

int binaryToDecimal(string n)
{
string num = n;
int dec_value = 0;

// Initializing base value to 1, i.e 2^0

int base = 1;

int len = num.length();

for (int i=len-1;i>=0;i--)
{
if (num[i] == '0')
{
dec_value += 0*base;
base = base * 2;
}
else
{
dec_value += 1*base;
base = base * 2;
}
}

return dec_value;
}

// Driver program to test above function

int main()
{
string num = "10101001";
cout<<binaryToDecimal(num)<<endl;
}

Sort an array of 0s, 1s and 2s

2.7
Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s
first, then all 1s and all 2s in last.
Example
Input = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};
Output = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}
Count Sort can be used here

Check if Number is palindrome or not :

n = num;

rev = 0;

while (num > 0)

dig = num % 10;

rev = rev * 10 + dig;

num = num / 10;

If n == rev then num is a palindrome:

cout << "Number " << (n == rev ? "IS" : "IS NOT") << " a palindrome" << endl;

Trapping Rain Water

3.6
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute
how much water it is able to trap after raining.
Examples:

Input: arr[] = {2, 0, 2}

Output: 2
Structure is like below

| |

|_|

We can trap 2 units of water in the middle gap.

Input: arr[] = {3, 0, 0, 2, 0, 4}

Output: 10

Structure is like below

| |

| | |

|__|_|

We can trap "3*2 units" of water between 3 an 2,

"1 unit" on top of bar 2 and "3 units" between 2

and 4. See below diagram also.

Input: arr[] = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

Output: 6

| || |

_|_||_||||||

Trap "1 unit" between first 1 and 2, "4 units" between

first 2 and 3 and "1 unit" between second last 1 and last 2
 Source: http://qa.geeksforgeeks.org/1875/trapping-rain-water

We strongly recommend that you click here and practice it, before moving
on to the solution.
An element of array can store water if there are higher bars on left and right. We can find amount of water
to be stored in every element by finding the heights of bars on left and right sides. The idea is to compute
amount of water that can be stored in every element of array. For example, consider the array {3, 0, 0, 2,
0, 4}, we can store two units of water at indexes 1 and 2, and one unit of water at index 2.
A Simple Solution is to traverse every array element and find the highest bars on left and right sides.
Take the smaller of two heights. The difference between smaller height and height of current element is the
amount of water that can be stored in this array element. Time complexity of this solution is O(n 2).
An Efficient Solution is to prre-compute highest bar on left and right of every bar in O(n) time. Then
use these pre-computed values to find the amount of water in every array element. Below is C++
implementation of this solution.

▪ C++
▪ Java
// C++ program to find maximum amount of water that can
// be trapped within given set of bars.

#include<bits/stdc++.h>

using namespace std;

int findWater(int arr[], int n)

{
// left[i] contains height of tallest bar to the
// left of i'th bar including itself

int left[n];

// Right [i] contains height of tallest bar to

// the right of ith bar including itself

int right[n];

// Initialize result
int water = 0;

// Fill left array

left[0] = arr[0];

for (int i = 1; i < n; i++)

left[i] = max(left[i-1], arr[i]);

// Fill right array

right[n-1] = arr[n-1];
for (int i = n-2; i >= 0; i--)

right[i] = max(right[i+1], arr[i]);

// Calculate the accumulated water element by element

// consider the amount of water on i'th bar, the

// amount of water accumulated on this particular
// bar will be equal to min(left[i], right[i]) - arr[i] .

for (int i = 0; i < n; i++)

water += min(left[i],right[i]) - arr[i];

return water;
 }

// Driver program
int main()

{
int arr[] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};

int n = sizeof(arr)/sizeof(arr[0]);

cout << "Maximum water that can be accumulated is "

<< findWater(arr, n);

return 0;

Run on IDE

Output:

Maximum water that can be accumulated is 6

Time Complexity: O(n)

Auxiliary Space: O(n)
Space Optimization in above solution :
Instead of maintaing two arrays of size n for storing left and right max of each element, we will just maintain
two variables to store the maximum till that point. Since water trapped at any element = min( max_left,
max_right) – arr[i] we will calculate water trapped on smaller element out of A[lo] and A[hi] first and move
the pointers till lo doesn’t cross hi .

▪ C++
▪ Java
// C++ program to find maximum amount of water that can
// be trapped within given set of bars.
// Space Complexity : O(1)

#include<iostream>

using namespace std;

int findWater(int arr[], int n)

{
// initialize output

int result = 0;

// maximum element on left and right

int left_max = 0, right_max = 0;

// indices to traverse the array

int lo = 0, hi = n-1;

while(lo <= hi)

{
if(arr[lo] < arr[hi])

if(arr[lo] > left_max)

// update max in left

left_max = arr[lo];

else

// water on curr element = max - curr

result += left_max - arr[lo];
lo++;

}
else
{

if(arr[hi] > right_max)

// update right maximum

right_max = arr[hi];

else
result += right_max - arr[hi];
hi--;

}
}
 return result;
}

int main()

{
int arr[] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};

int n = sizeof(arr)/sizeof(arr[0]);
cout << "Maximum water that can be accumulated is "

<< findWater(arr, n);

// This code is contributed by Aditi Sharma

Run on IDE

Output:

Maximum water that can be accumulated is 6