## Friday, May 31, 2013

### How does Bubble sort works?

Bubble sort is a comparison based sorting algorithm. It works like following.
We perform series of iterations to 'bubble up' the elements one by one so that they form a sorted order. For example we have to sort an array [3,1,4,5,2] in ascending order, In the first iteration, the element 5 will be bubbled up to the last spot. In the second iteration element '4' will be moved to the last but first spot and so on. The following sequence shows one iteration. In each step in the iteration, successive pairs of elements are compared, if they violate the order, swap it.

3<->1 4 5 2
1 3<->4 5 2
1 3 4<->5 2
1 3 4 5<->2
1 3 4 2 5

This iteration is repeated until the entire array is sorted. In the first iteration, there will be n-1 comparisons. In the second iteration there will be n-2 comparisons. The number of comparisons decreases with each iteration. The last iteration will have only one comparison. The following code shows the implementation of the above approach. The time complexity of bubble sort is O(n^2).
` `
```#include <iostream>
using namespace std;

//helper method to swap two elements
void swap( int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
//bubble sort function, takes array and it's size
//as parameters
void bubble_sort(int *array, int n)
{
int i,j;
//outer loop runs for n-1 iterations
for( i = 0 ; i < n-1 ; i++)
{
//inner loop is for comparisons
//in each iteration comparisons reduce by 1
for( j = 0 ; j < n-1-i ; j++)
{
//if elements are out-of-order, swap them
if( array[j] > array[j+1] )
swap(array[j], array[j+1]);
}
}
}
int main()
{
int n;
cin>>n;
int *array = new int[n];
int i;
for( i = 0 ; i < n ; i++ )
{
cin>>array[i];
}
bubble_sort(array,n);
for( i = 0 ; i < n ; i++)
{
cout<<array[i]<<" ";
}
return 0;
}```
` `
In bubble sort there is a mechanism to detect if the input array is already sorted. In any iteration, if there are no swappings performed, then we can conclude that the array is sorted. Here is how we can modify the bubble sort to implement this.

```void bubble_sort(int *array, int n)
{
int i,j;
bool swap_flag = false;
//outer loop runs for n-1 iterations
for( i = 0 ; i < n-1 ; i++)
{
//inner loop is for comparisions
//in each iteration the comparisions count reduce by 1
for( j = 0 ; j < n-1-i ; j++)
{
//if elements are out-of-order, swap them
if( array[j] > array[j+1] )
{
swap(array[j], array[j+1]);
swap_flag = true;
}
}
//if no swaps are performed in the inner loop, break
if( !swap_flag )
break;
}
}
```

## Thursday, May 30, 2013

### Program to find GCD of two numbers

In mathematics, the greatest common divisor (gcd), also known as the greatest common factor (gcf), or highest common factor (hcf), of two or more integers (at least one of which is not zero), is the largest positive integer that divides the numbers without a remainder - from Wikipedia
For example, the GCD of 8 and 12 is 4
Euclidian method: This is also called division algorithm. Take smallest of the two numbers and divide the other number. If the remainder is zero smaller number is the GCD. Otherwise replace the smaller number with remainder, and bigger number with present smaller number and repeat the same procedure.

Here is the step-by-step calculation

8)12(1
8
----
4)8(2
8
---
0

The following c++ code implements the iterative and recursive version of Euclidian algorithm.

```#include <iostream>

using namespace std;
void swap(int &x, int &y)
{
int temp = x;
x = y;
y = temp;
}
//iterative version of Euclidian algorithm
int gcd(int x,int y)
{
while ( (y % x) != 0)
{
int r = y % x;
y = x;
x = r;
}
return x;
}
//recursive version of Euclidian algorithm
int gcd_recursive(int x, int y)
{
if( y % x == 0)
return x;
return gcd_recursive( y%x, x);
}

int main()
{
int x,y;
cin>>x>>y;
//both iterative and recursive versions requires first parameter <= second
//swap if firt is greater
if( x > y )
{
swap(x,y);
}
cout<<"GCD(" << x << "," << y << ")=" << gcd_recursive(x,y) << endl;
return 0;
}
```

## Friday, May 24, 2013

### Finding the length of a linked list

In this post we will see an algorithm to find the length of the linked list. Here singly linked list is implemented in Object Oriented Programming (OOP) paradigm in C++. The algorithm is very simple. Just start at the beginning of the linked list, move to next until you reach the end of the list, incrementing a counter in each iteration. Following is the source C++ code for the same.

```#include <iostream>

using namespace std;

//Node definition for a single linked list
class SLLNode
{
private:
//data member
int data;
//pointer to next node in the linked list
SLLNode *nextPtr;

public:

//Single argument constructor
//initializes data with d, next pointer to NULL
SLLNode(int d):data(d),nextPtr(NULL)
{
}
//to initialize both members
SLLNode(int d,SLLNode* next):data(d),nextPtr(next)
{
}
//returns the data
int getData()
{
return data;
}
//sets the data
void setData(int d)
{
this->data = d;
}
//gets the next pointer
SLLNode* getNext()
{
return this->nextPtr;
}
//sets the next pointer
void setNext(SLLNode *ptr)
{
this->nextPtr = ptr;
}
};

//defines the actual single linked list
{
private:
//maintain two pointers to the start and the end
//so that we can append at the end easily (constant time complexity)
SLLNode * tail;
public:
{
tail = NULL;
}
//adds the node to the end of the list
void appendNode(SLLNode* ptr)
{
//check if list is empty
{
//update both the pointers
}
else //simply append at the end, and move the tail pointer
{
tail->setNext(ptr);
tail = tail->getNext();
}
}
//gets the length of the list
int getLength()
{
int length = 0;

while ( ptr != NULL )
{
length++;
ptr = ptr->getNext();
}
return length;
}
};

int main()
{
list.appendNode(new SLLNode(1));
list.appendNode(new SLLNode(2));
list.appendNode(new SLLNode(3));
list.appendNode(new SLLNode(4));
cout<<"Length: "<<list.getLength()<<endl;
return 0;
}
```

## Thursday, May 23, 2013

### Member initialization list in C++

You all know that in C++, constructors are used to create an object. We normally initialize all the data members with some valid data in the constructor. We generally write code similar to the following and think that m_data variable is being initialized where as it is actually being assigned.

```class MyClass
{
public:
Myclass(int d)
{
m_data = d;
}
private:
int m_data;
}```
` `

To actually initialize a data member, we need to use member initialization list in C++. Using member initialization list, the constructor is written as follows

```class MyClass
{
public:
Myclass(int d):m_data(d)
{
}
private:
int m_data;
}```
` `

Here we specified the member initialization list after constructor name followed by colon (:) If multiple members are present, they are separated by Comma. like m_data1(d1), m_data2(d2). In this case the members are initialized before entering the constructor itself.

What happens in the first case?  The default constructor (that is provided by the compiler) is called to initialize non-primitive data types before entering the written constructor. All the primitive type data members like int, char, float are not guaranteed to get initialized in the default constructor.

## Wednesday, May 22, 2013

### Finding the missing element in an array:

An array of size (n-1) contains all the numbers in the range [1..n] except one number which is missing. Write a program to find the missing number in O(n) time and O(1) space.

For example let N= 5 and the input array is [1,3,4,5], the output should be 2.

Given O(n) space we can always maintain a boolean array of size n to store a flag for each number if it is present or not. Here the restriction is to use constant extra space.

Two methods are discussed here.

Method#1:
Find sum of all the elements in given array. Let it be sum1. Find the sum of numbers from 1 to n. It would be
n*(n+1)/2 (remember Arithmetic Progression from your school mathematics?) let it be sum2. Now subtracting sum1 from sum2 ( sum2-sum1) gives the required result.
Method#2:
Find XOR of all the elements in the array, let it be ax. Find XOR of elements from
[1..n], let it be nx. Then performing XOR between these two gives the missing number

The following C++ code shows the implementation of both the methods stated above. Both algorithms run in O(n) time and O(1) space complexity.

```#include <iostream>
using namespace std;
//array contains n-1 numbers, this method finds
//the nth number missing.
int findMissingNum(int *array, int n)
{
//sum of first n numbers 1...n
int nSum = n*(n+1)/2;
//find array sum
int arSum = 0;
for( int i = 0 ; i < n-1 ; i++)
{
arSum += array[i];
}
// difference between two sum, gives the missing number
return nSum - arSum;
}

int findMissingNumXor(int *array,int n)
{
int nXor; //XOR of 1..N elements
int arXor; //XOR of array elements
int i;
//find XOR of 1 to n elements
for( i = 0 ; i < n ;i++)
{
nXor = nXor ^ (i+1);
}
//find XOR of array elements
for( i = 0 ; i < n-1 ; i++)
{
arXor = arXor ^array[i];
}
//XOR of two gives the result
return nXor ^arXor;
}
int main()
{
int *array;
int n;
cin>>n;
//allocate memory for n-1 numbers
array = new int[n-1];
int i;
for( i = 0; i < n-1; i++)
{
cin>>array[i];
}

cout<<findMissingNumXor(array,n);
//deallocate dynamic memory
delete[] array;
return 0;
}
```

## Friday, May 17, 2013

### Couple elimination problem

Given a string of some symbols, write a program to transform a string by repeatedly eliminating two same symbols occurring together.
For example if the input string is 'RGGB' it will be reduced to 'RB' because 'GG' can be eliminated.

Here are some more examples of input - output

Input   | Output
-------------------
GBRRBR  | GR
BGRGRR  | BGRG
GGBB    | <empty>
RGBGBR  | RGBGBR

Here is how we can solve this problem. Add each character into a temporary array. As you insert the character, check for previously inserted character. If it is same, erase that character otherwise add it to the temporary array. At the end, the temporary array has the transformed string.

C++ implementation of the above approach is given below.

` `
```#include <iostream>
#define MAX 100
using namespace std;

int main()
{
char string[MAX];
char temp[MAX];

cin>>string;
int i;
int tempInd = 0; //to track temp string

for( i = 0 ; string[i] != '\0' ; i++)
{
//If temp string has atleast one character
if( tempInd > 0)
{
//If previous, and current chars are same, erase
if( temp[tempInd-1] == string[i] )
{
tempInd--;
}
else//not same, append the char to temp
{
temp[tempInd++] = string[i];
}
}
else //temp is empty, simply append the character
{
temp[tempInd++] = string[i];
}
}
//append the NULL character at the end
temp[tempInd] = '\0';
//print the transformed string
cout<<temp<<endl;
return 0;
}
```

## Wednesday, May 15, 2013

### Replacing spaces in a character array with %20

Given a character array which contains some spaces. we have to replace all the spaces with the string '%20'. This algorithm is commonly used during HTML encoding of the URLs in the web browsers. Assume that the array has enough space at the end to accommodate the expanded string, how do we do this efficiently?

The following solution uses no extra space and runs in O(n) time. The trick here is to start copying the characters from the end, and wherever we find space replace it with '%20'. The following C++ code does exactly that.

```#include <iostream>
#define MAX 100
using namespace std;

void replaceSpace(char *array)
{
int len=0,i;
int spaceCount = 0;
//this loop calculates the spaces and length of the string
for( i = 0 ; array[i] != '\0' ; i++ )
{
//count spaces
if( array[i] == ' ')
spaceCount++;
//update length
len++;
}
//array has enough space, try to copy the string from end
//end index will be length + 2*no of spaces bcoz for each space
//there will be (3-1=2) two additional characters inserted
int resInd = len + 2*spaceCount;

//len is the index of '\0' (i.e last) in the original string
//start copying from there
while ( len >= 0)
{
//if space, insert %20 in reverse, bcoz we are copying from reverse
if( array[len] == ' ')
{
array[resInd--] = '0';
array[resInd--] = '2';
array[resInd--] = '%';
}
else //copy as it is
{
array[resInd--] = array[len];
}
len--;
}
}
int main()
{
char chArray[MAX];
gets(chArray);
replaceSpace(chArray);
cout<<chArray<<endl;
return 0;
}
```

## Tuesday, May 14, 2013

### Common elements between two sorted arrays

Given two sorted arrays, how do you efficiently find the common elements between those two?

Method#1:
Simple and Brute-force approach
Iterate through one array, and try to find the element in another array using linear search. If it is found, then print it. This approach takes O(n^2) time as for each element in the first array we doing a linear search in the second array which takes O(n). So for n elements it would be O(n^2).

Method#2:
Better approach with binary search
This approach is simliar to the first one except that it uses binary search instead of linear search for finding an element in the second array as the arrays are sorted. Binary search takes O(log n) for each element. So for n elements the time complexity would be O(n log n).

Method#3:
Efficient
This method fully utilizes the fact that both arrays are sorted. Start with two indices pointing to beginning of the arrays. If the elements pointed by these indices are same, then it is a common element, and we advance both the pointers. If one element is smaller, then advance that pointer (in hope of finding the next equal element). Continue this until any one of the two indices reaches their end.

Here is the C++ code which implements the third approach.

```#include <iostream>
#include <string>
#include <vector>

using namespace std;

//prints the intersection of two sorted arrays
//duplicates are allowed
void printIntersect(vector<int>& s1, vector<int>& s2)
{
//i and j start 0 i.e first element
int i = 0 , j= 0;

//while either of the two indices reaches end
while ( i < s1.size() && j < s2.size() )
{
//if first array element is lesser, advance that index by one
if( s1[i] < s2[j] )
{
i++;
}
else if( s1[i] > s2[j] )
{
j++;
}
//both elements are same, print it, and advance both the pointers
else
{
cout<<s1[i]<<" ";
i++;
j++;
}
}
}

int main()
{
vector<int> set1, set2;
int n1,n2; //size of the sets
cin>>n1>>n2;

int i;
for( i = 0 ; i < n1; i++ )
{
int d;
cin>>d;
set1.push_back(d);
}
for( i = 0 ; i < n2; i++ )
{
int d;
cin>>d;
set2.push_back(d);
}
printIntersect(set1,set2);
return 0;
}
```

## Monday, May 13, 2013

### Rotating an array:

In this post we will discuss two solutions for rotating an array by a given number of times. One is a simple solution and another uses the reversal operation (discusses in the previous post).

Method#1: Simple and intuitive
In this method, we will copy the last element into a variable, and shift all the elements right by one step, and copy the stored element into the empty spot created at the beginning of the array. We repeat this for the given number of times.

Method#2: Using reversal algorithm
I have taken this algorithm from here. It is a three step procedure. Let array[0:n-1] be the array, and 's' be the number of times to rotate the array.
step 1: Reverse the sub-array array[0:s-1]
step 2: Reverse the sub-array array[s:n-1]
step 3: Reverse the whole array i.e array[0:n-1]

For example let the array be [7 1 2 3 8], and it is to be rotated 3 times
here is how it works
step 1: [2 1 7 3 8]
step 2: [2 1 7 8 3]
step 3: [3 8 7 1 2]

C++ implementation of the above two methods is given below.

```#include <iostream>
#include <string>

using namespace std;

//right rotates array of size n by s positions
//assumes that n > 1 (atleast 2 elements) and s < n
void rotateSimple( int* array, int n, int s)
{
int i;
int j;
for( i = 0 ; i < s ; i++ )
{
//store the last element
int last = array[n-1];

//shift all elements right by one
for( j = n-2 ; j >= 0 ; j-- )
{
array[j+1] = array[j];
}
//copy stored element to the beginning
array[0] = last;
}
}
//helper method for reversal
void swap( int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}

//function to reverse the sub-array array[low to high
void reverseArray(int *array, int low, int high)
{
while( low < high ) //until both ends meet
{
swap( array[low], array[high] ); //swap the elements
low++; //increment left
high--;//decrement right
}
}
//rotate the array using reversal operation
void rotateByReverse(int* array,int n, int s)
{
reverseArray(array,0,s-1);
reverseArray(array,s,n-1);
reverseArray(array,0,n-1);
}

//utlity to print the array
void printArray(int * array,int n)
{
for( int i = 0; i < n; i++ )
{
cout<<array[i]<<" ";
}
cout<<endl;
}

int main()
{
int n; //array size
int s; //rotation count
//read array size, and rotation count
cin>>n>>s;
//dynamically allocate array based on input size
int *array = new int[n];
int i;
for( i = 0 ; i < n; i++ )
{
cin>>array[i];
}
//call rotate function
rotateByReverse( array, n, s);
printArray( array, n);
//release the memory
delete[] array;
return 0;
}
```

## Friday, May 10, 2013

### Reversing an array

In this post we will discuss a simple problem on Arrays. Given an array of numbers, how do we reverse it efficiently?

Here is the simple and effective approach. We start with one index pointing to the start, and another index pointing to the end of the array. We swap the two elements at these indices, increment left index, and decrement right index. We continue this procedure until both indices meet each other. Then we stop. At the end, the array is reversed.

For example, let us consider the array with 5 elements, Here is how it works

Array: [1  2  3  4  5] - swap
|           |
left       right

[5  2  3  4  1] - swap
|     |
left  right

[5  4  3  2  1] - stop
|
left
right

` `
```#include <iostream>
#include <string>

using namespace std;

void swap( int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
//function to reverse the array
void reverseArray(int *array, int n)
{
int low = 0; //initialize low to first element
int high = n-1; //initialize high

while( low < high ) //until both ends meet
{
swap( array[low], array[high] ); //swap the elements
low++; //increment left
high--;//decrement right
}
}
void printArray( int *array,int n)
{
for(int i = 0 ; i < n;i++ )
{
cout<<array[i]<<" ";
}
cout<<endl;
}
int main()
{
int n;
cin>>n;
int* array = new int[n];
int i;

for( i = 0 ; i < n ; i++)
{
cin>>array[i];
}
reverseArray( array, n);
printArray( array, n);
return 0;
}
```

## Wednesday, May 8, 2013

### Bracket matching problem

Stack is one of the most widely used data structure. In this post we will learn how to use the stack container (data structure) provided by C++ STL with an example.

Let us consider the following problem. We have a string which contains only '(' and ')' characters. We have to write a program to check if it forms a valid expression.
For example the string "(()())" is a valid expression where as "(()()" and "())" are not.

The algorithm for solving the question goes like this.

1. For each character in the string
If the symbol is '('
push it on to the stack
else
If the stack is empty
return false
If top of the stack contains '('
pop off the top element
2. If the stack is empty return true otherwise return false

Here is the program which implements the above algorithm.

```#include <iostream>
#include <string>
#include <stack>

using namespace std;

bool isValidExpr(string input)
{
stack<char> stck;

for(int i = 0; i < input.length() ; i++)
{
char ch = input.at(i);

if( ch == '(' ) //if open brace, push
{
stck.push(ch);
}
else //closed brace
{
if( stck.empty() )// if stack is empty, there no matching open brace
return false;
if ( stck.top() == '(' ) //matching open brace found, so pop
{
stck.pop();
}
}
}
if( stck.empty() )
return true;
return false;
}

int main()
{
string inputExpr;
cin>>inputExpr;
if( isValidExpr(inputExpr) )
cout<<"Valid Expression";
else
cout<<"Invalid Expression";
return 0;
}
```

## Tuesday, May 7, 2013

### Counting characters in the given string using C++ STL map

Map is one of the most useful data structure in solving many programming problems. Today we will see how to use C++ STL map with a simple example. Counting the frequency of letters in a given string. The map data structure stores <key,value> pairs. In this example key will be the character, and the value will be it's frequency. Here is the code to do this.

```#include <iostream>
#include <string>
#include <map>

using namespace std;

void getFrequency(string strInput,map<char,int> & fMap)
{
map<char,int>::iterator it; //iterator to find the entries in map
for(int i = 0 ; i < strInput.length() ; i++ )
{
char ch = strInput.at(i);
it = fMap.find(ch); //find the character in the map
if( it == fMap.end() ) //if not present in the map
{
}
else
{
it->second++; //else increment the frequency
}
}
}

void printFrequency(map<char,int> & fMap)
{
map<char,int>::iterator it;//iterator to loop through all the chars
for( it = fMap.begin() ; it != fMap.end() ; ++it )
{
cout<<"["<< it->first<<"]"<<"->"<<it->second<<endl;
}
}

int main()
{
string strInput;
//read input string; this implementation does not reed space separated strings
cin>>strInput;
map<char,int> frequencyMap; //frequency map
getFrequency(strInput, frequencyMap); //get the frequencies
printFrequency(frequencyMap); //print the frequencies
return 0;
}
```

## Monday, May 6, 2013

### Finding count of a number in a sorted array

In Competitive programming, learning to use the standard library than coding from scratch saves a lot of time. In this post we will use C++ STL(Standard Template Library) binary search algorithm with an example.
Given a sorted array of numbers, How to find the frequency of a given number?

Here is an efficient algorithm to do it. Use binary search to find the left-most(L), and right-most(R) occurrence of the given number. Then R-L+1 gives us the result.

C++ STL has two functions namely lower_bound, upper_bound which finds out the left-most and right-most occurrences of a given number in a sorted array.
The lower_bound() function returns an iterator to the left-most element, and the upper_bound() function returns an iterator to one element beyond right-most occurrence. So the difference of these two gives the count.

Here is the C++ code.

```#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int getCount(vector<int> & numVector, int d)
{
int result = 0;
vector<int>::iterator left, right;
//find the left-most occurence
left = lower_bound( numVector.begin(), numVector.end(), d );
//find right-most occurence only if the number is present
if( left != numVector.end() )
{
right = upper_bound( numVector.begin(), numVector.end(), d );
result = right-left; //right points to one element beyond.
}
return result;
}
int main()
{
int n;
cin>>n;
int i,num;
vector<int> nums;
for( i = 0 ; i < n ; i++ )
{
cin>>num;
nums.push_back(num);
}
//read the number to be counted
cin>>num;
cout<<getCount(nums,num);
return 0;
}
```

### Finding duplicates from given set of numbers

Given a list of numbers. How do we write a program to find the duplicates among them?
A simple algorithm is to compare each possible pair in the list to see if there are any duplicates. But this algorithm runs in O(n2) time.
We can use the following simple algorithm using the set data structure. This data structure supports insert/add, find operations. We read one number at a time and try to find it in the set. If the set already contains that element, we declare that element as a duplicate, otherwise we insert that element into that set. The following is a Java implementation of the same.

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43``` ```import java.io.*; import java.util.HashSet; /** * * @author Ravi */ public class DuplicateNums { /** * @param args the command line arguments */ public static void main(String[] args) { try { //Read from the standard input BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String input = br.readLine(); String [] strNums = input.split(" "); //create the hash set to store the unique numbers HashSet hSet = new HashSet(); for( int i = 0 ; i < strNums.length ; i++) { //try to add the number to the set, //if add method returns false, the number is a duplicate if( !hSet.add( Integer.parseInt(strNums[i]) ) ) { System.out.print(strNums[i] + " "); } } System.out.println(); } catch(IOException ioe) { System.out.println("Exception while reading the input" + ioe.getMessage()); } catch(NumberFormatException nfe) { System.out.println("Invalid Input "+ nfe.getMessage()); } } } ```

We have used HashSet data structure from the Java standard library. This provides O(1) time for insert and find operations in an average case. So the average time complexity of the above program is O(n). Since we are storing the elements in the set, the space complexity is O(n) in the worst case (No duplicates in the list).