// Program to find elements that are common in 3 sorted arrays
#include <iostream>
using namespace std;
// This function finds common elements
int searchCommon(int arr1[], int arr2[], int arr3[], int l1, int l2, int l3)
{
int i=0,j=0,k=0;
while(i<l1 && j<l2 && k<l3)
{
if(arr1[i]==arr2[j] && arr2[j]==arr3[k])
{
cout<<arr1[i]<<" ";
i++;
j++;
k++;
}
else if(arr1[i]<arr2[j])
{
i++;
}
else if(arr2[j]<arr3[k])
{
j++;
}
else
k++;
}
}
// main function
int main()
{
int ar1[] = {4,19,33,47,68,79,82,85,100};
int ar2[] = {18,19 ,20,33,79, 80, 100};
int ar3[] = {1,2,4,33,64,68,79,100,128,139};
int l1 = sizeof(ar1)/sizeof(ar1[0]);
int l2 = sizeof(ar2)/sizeof(ar2[0]);
int l3 = sizeof(ar3)/sizeof(ar3[0]);
cout << "Elements that are common : ";
searchCommon(ar1, ar2, ar3, l1, l2, l3);
return 0;
}
Tuesday, 28 July 2015
Find common elements in 3 sorted arrays - C++ code
Find common elements in 3 sorted arrays
Find common elements
in 3 sorted array
3 arrays are given:
Arr1: 4,19,33,47,68,79,82,85,100
Arr2: 18,19 ,20,33,79, 80, 100
Arr3: 1,2,4,33,64,68,79,100,128,139
Out of all these,
33,79,100 are the elements that are common in given 3 arrays.
Brute force approach :
Pick first element in arr1 and check
if it is present in 2nd and 3rd array also. If yes then
print it, otherwise pick second element, then third element and so on.
Time complexity : O(n3 )
An efficient approach :
Algorithm :
Step 1: Initialize i=0,j=0,k=0;
Step 2 :Repeat this step till i<len(arr1) and j<len(arr2) and
k <len(arr3)
A)If
arr1[i]=arr2[j]=arr3[k] ,print that element as it is the common element and
increment i,j,k.
B) Else if arr1[i] <
arr2[j] ,then arr1[i] cannot be the common element of 3 arrays as arr2 has
already moved ahead. Increment i.
C) Else if arr2[j]<
arr3[k] , then arr2[j] cannot be the common element. Increment j.
D)Else increment k. We
will reach to this case when arr1[i] > arr2[j] and arr2[j] > arr3[k] .It
means arr3[k] is smallest. So it cannot be the common element.
Time complexity: O(n)
Auxiliary space: O(1)
Monday, 27 July 2015
Traversal in binary tree
Traversals in
Binary Tree
Before reading this, please
check out our video https://www.youtube.com/watch?v=FFOTq1RcrBE to fully
understand what a binary tree actually is.
Now, you must be wondering
that how can we print the data of the tree or how can we actually go to each
node in the tree. So, traversals are the systematic way through which we can
travel to each node in the tree exactly once that too in some systematic
behavior.
The linear order, which traverses
from beginning to end, is not present in the trees.
The different traversals
present for the tree are -
1. Preorder
Traversal
2. Inorder Traversal
3. Postorder
Traversal
4. Level Order
Traversal
Remember that binary tree is
of recursive nature, means that the left and right sub trees of the binary tree
root node are themselves the binary trees and this property helps us achieve
the traversals using the recursion method.
1. Pre order
Traversal-
Steps.
i.
Visit the root
ii.
Traverse the left sub tree in pre order manner
iii.
Traverse the right sub tree in pre order manner
2. In order
traversal
Steps
i.
Traverse the Left sub tree in in order fashion
ii.
Visit the root
iii.
Traverse the right sub tree in in order fashion
3. Post Order
Traversal
Steps
i.
Traverse the left sub tree in post order fashion
ii.
Traverse the right sub tree in post order fashion
iii.
Visit the root
We will discuss the level
order traversal later.
In all the above three
traversals, we can see that the steps involve the traversing the left and right
sub trees in some particular fashion, and here at these steps is when we call
it recursively.
Recursive
implementation of the Traversals –
Structure
of node of a tree
struct node
{
int data;
node *left; //left
child
node *right; //right
child
};
1.
Preorder
void preorder(node *n)
{
if(n==NULL) return ;
// if node is NULL or becomes NULL simply return
//acts as base case
printf("%d\t", n->data); // print the root
preorder(n->left); // recurse over left sub tree
preorder(n->right); //recurse over right sub tree
}
2.
Inorder
void inorder(node * n)
{
if(n==NULL) return ;
inorder(n->left); // recurse over left first
printf("%d\t", n->data); // print node ->data
inorder(n->right); // now recurse over right sub tree
}
3.
Postorder
void postorder(node *n)
{
if(n==NULL) return ;
postorder(n->left);
postorder(n->right);
printf("%d\t", n->data);
}
Time Complexity – O(n) , n =
#nodes in the tree
Space Complexity – O(n) –
considering the stack used in the recursion
Iterative
implementations of the Traversals-
1.
Preorder
void preorderi(node *n)
{
if(n==NULL)
return;
stack<node *>s; // make an explicit stack
s.push(n); //push root node
into it
while(!s.empty()) // while stack has nodes
{
node *temp = s.top(); //print parent/node data
cout<<temp->data;
s.pop();
//push its left and right
children but in opposite order as stack works in LIFO manner
if(temp->right)
s.push(temp->right);
if(temp->left)
s.push(temp->left);
}
}
2.
Inorder
i.
Create an empty stack
ii.
push root node and make it the current node
iii.
keep on pushing node till current does not become
NULL, right now the topmost element in stack is the first node to be printed in
inorder traversal
iv.
now till the stack does not become empty , keep on
popping the top print it and move to the popped node’s right
void inorderi(node *n)
{
if(n==NULL)
return;
stack<node *> s;
int done =0;
while(!done)
{
if(n!=NULL)
{
s.push(n);
n=n->left;
}
else
{
if(!s.empty())
{
n
= s.top();
printf("%d \t",
n->data);
s.pop();
n=n->right;
}
else
{
done =1;
}
}
}
}
3.
Postorder
A little difficult due to
non-tail recursion present in it. We simply generate the reverse Postorder and
store it in the stack and using the LIFO property we print the correct
Postorder traversal.
You may now think that how
to generate the reverse Postorder.
Lets try it out on an
example –
The Postorder traversal is –
4, 5, 2 , 6 , 7 , 3 ,1
The reverse Postorder
Traversal is – 1, 3, 7, 6, 2, 5, 4
We need to get this into the
stack. But Question still remains same … How ??
Let us check Preorder Traversal
– 1, 2, 4, 5, 3, 6, 7
We know that in preorder
first the left subtree is recursed and then right sub tree.
But suppose if we change it
to first recurse over right sub tree and then to over left sub tree
Changed preorder traversal –
1, 3, 7, 6, 2, 5, 4
And now you can easily see
that this changed preorder and reverse post order traversal we want are the
same.
So for iterative Postorder,
we go like preorder with two little changes
i.
Recurse over left first and right later ( remember
context of Stack -LIFO)
ii.
Instead of printing the data, store it in the stack
iii.
At last print the stack
Two stacks will be needed,
one for holding the reverse Postorder and other for iterating over the nodes.
void postorderi(node *n)
{
if(n==NULL)
return;
stack<node *>s1;
stack<node *>s2;
s1.push(n);
while(!s1.empty())
{
node *temp = s1.top();
s1.pop(); //popping form s1
s2.push(temp); //pushing to s2
if(temp->left)
s1.push(temp->left);
//remember LIFO
if(temp->right)
s1.push(temp->right);
}
while(!s2.empty())
{
node *t = s2.top();
printf("%d\t", t->data);
s2.pop();
}
}
These all are the DFS kind
of traversals.
There also exist BFS kind of
traversal known as level order traversal.
We will discuss it soon.
Till time practice these.
For any queries or problems
or future updates, kindly subscribe to our YouTube Channel
Any Queries or
updates or any problem in document or the Videos that you may want to discuss
you can follow our twitter account - https://twitter.com/Logic_Heap
Finding closest pair of points
Algorithm – Finding closest pair of points
Technique – using Divide and Conquer strategy
Problem – We are given a set of points and we have to find the minimum distance between all the
Points.
Solution-
1. Naïve Approach – we can loop through all the set of points one by one for each point.
Algorithm –
float distance( point p1, point p2) //distance between two coordinates
{
return sqrt((p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));
}
float naive(point p[], int n) // point is the structure having x , y as members(coordinates)
//& n = total number of points available
{
int i , j ;
float min=FLT_MAX; // defined constant
float dist;
for(i=0;i<n;i++) // iterating through each point
{
for(j=i+1;j<n;j++) // for each point check its distance from remaining points
{
dist = distance(p[i], p[j]);
if(dist < min)
min = dist;
}
}
return min;
}
Time Complexity – O(n^2)
2. Divide and Conquer Approach – we can better the naïve approach using divide and conquer strategy.
Steps –
Pre- processing step - Sort the given points according to the x coordinates.
1. Find the middle point.
2. Recursively find the minimum distance in the left and right sub arrays.
Understand this step – we can find the minimum distance either on the left side of the mid-point (left sub array) or on the right side (right sub array) or we can find minimum on the points among which one is in the left sub array and another in the right sub array.
3. Among both the minimums (from left and from right), find the minimum, let us call it d.
4. Now comes the important step-
We find those points whose distance is less than d from the middle point (found in 1.) in both (left and right) directions
As only these could be the candidates for those points whose distance is closest.
5. Sort these points according to the y coordinate
6. Find the minimum among all these points using the naïve approach but it is been proved that inner loop runs at most 6 times.
(check this- http://people.csail.mit.edu/indyk/6.838-old/handouts/lec17.pdf) .
7. Now find the minimum between the point found in 7 and d.
Time Complexity – time for divide and conquer – 2T(n/2) // as dividing into two sub parts of n/2
// size
+ time for finding the points having distance < d (step 4) – O(n)
+ time to sort( step 5) – O(nlogn)
+ step 6 – O(n) because the inner loop runs at most 6 times
=) O(nlognlogn)
Algorithm -
struct point // point representation
{
int x, y;
};
// for sort stl
int cmpx(const point& p1, const point& p2)
{
return (p1.x<p2.x);
}
int cmpy(const point& p1, const point& p2)
{
return (p1.y<p2.y);
}
// step 5 & 6 , strip is the array consisting of “certain points” from left and right sub arrays
float stripclosest(point strip[] , int j ,float d)
{
// d is the min (corresponding to min of naive)
// j - #points in strip
//5. sort strip acc to y coordinates
sort(strip, strip+j, cmpy);
int n =j;
float dist;
//6. find minimum using naive approach .. it takes O(n) not O(n^2) because inner loops
// runs atmost 6 times
for(int i=0;i<n;i++)
{
// if distance of points is less than d , only then consider otherwise no need as that pair can never
// be closest point(obviously)
for(int k=i+1;k<n && abs(strip[k]. y - strip[i].y) < d; k++)
{
dist = distance(strip[i], strip[k]);
if(dist < d) // if less than the considered minimum
{
d = dist;
}
}
}
return d ;
}
float closestutil(point p[], int n)
{
// Base Case
if(n<=3)
return naive(p, n);
//2. find mid point
int mid = n/2;
point m = p[mid];
//3a. recursively find minimum in left and right sub arrays
float dl = closestutil(p, mid);
float dr = closestutil(p+mid, n-mid);
//3b. find minimum among both
float d = minimum(dl, dr);
//4. make an array strip and store the point having distance <d from point m
point strip[n];
int j=0;
for(int i=0;i<n;i++)
{
// take only if the distance of point is less than d from the middle line(point) as only they can be the //candidates for the points having closest distance
if(abs(p[i].x-m.x) < d)
{
strip[j]=p[i];
j++;
}
}
// calculating smallest distance in strip and finding minimum among d(min of left and right and min //distance in strip(min if the closest distance is present in subarray crossing some part of left and //right sub array)
return minimum(d, stripclosest(strip, j, d, a));
}
float closest(point p[], int n)
{
//1. sort the points acc to x coordinate
sort(p, p+n, cmpx);
return closestutil(p,n);
}
Before going further do try to code it and if any problem occurs or you have any doubt regarding any thing related to the algorithm or any query please kindly tell us either on our Facebook Group
https://www.facebook.com/groups/logicheap/or you can follow our twitter account - https://twitter.com/Logic_Heap
For more such algorithms and many more videos and stuff related to algorithms of data structures, kindly subscribe to our YouTube channel -https://www.youtube.com/watch?v=FFOTq1RcrBE
Implementation in C++
// prints distance and corresponding points also
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
struct point
{
int x, y;
};
// for qsort stl
int cmpqx(const void* u, const void* v)
{
point *p1 =(point*)u;
point *p2= (point*)v;
return (p1->x - p2->x);
}
int cmpqy(const void* u, const void* v)
{
point *p1 =(point*)u;
point *p2= (point*)v;
return (p1->y - p2->y);
}
// for sort stl
int cmpx(const point& p1, const point& p2)
{
return (p1.x<p2.x);
}
int cmpy(const point& p1, const point& p2)
{
return (p1.y<p2.y);
}
float minimum(float i, float j)
{
return (i<j?i:j);
}
float distance( point p1, point p2)
{
return sqrt((p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));
}
void printpoint(point a[])
{
cout<<"\n"<<a[0].x<<" "<<a[0].y;
cout<<"\n"<<a[1].x<<" "<<a[1].y;
}
//O(n^2)
float naive(point p[], int n, point a[])
{
int i , j ;
static float t=INT_MAX;
// making it static is necessary otherwise suppose that min is found in left subarray and now right //subarray is called and t will not hold the previous min value and calculate the min and point array //will be wrong
//I advise you to go and remove static and execute and you will understand the power of static //yourself.
float dist;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
dist = distance(p[i], p[j]);
cout<<"\n checking t="<<t;
if(dist < t)
{
t = dist;
a[0].x = p[i].x;
a[0].y = p[i].y;
a[1].x = p[j].x;
a[1].y = p[j].y;
}
}
cout<<"\n checking returning t ="<<t;
return t;
}
float stripclosest(point strip[] , int j ,float d, point a[])
{
// d is the min (corresponding to min of naive)
// j - #points in strip
//5. sort strip ac to y coordiantes
qsort(strip, j , sizeof(point), cmpqy);
//sort(strip, strip+j, cmpy); , you can use any but qsort is better
int n =j;
float dist;
//6. find minimum using naive approach .. it takes O(n) not O(n^2) because inner loops
// runs atmost 6 times
for(int i=0;i<n;i++)
{
for(int k=i+1;k<n && abs(strip[k]. y - strip[i].y) < d; k++)
{
dist = distance(strip[i], strip[k]);
if(dist < d)
{
d = dist;
a[0].x = strip[i].x;
a[0].y = strip[i].y;
a[1].x = strip[k].x;
a[1].y = strip[k].y;
}
}
}
return d ;
}
float closestutil(point p[], int n, point a[])
{
if(n<=3)
return naive(p, n, a);
//2. find mid point
int mid = n/2;
point m = p[mid];
//3a. recursively find minimum in left and right sub arrays
float dl = closestutil(p, mid,a);
float dr = closestutil(p+mid, n-mid,a);
//3b. find minimum among both
float d = minimum(dl, dr);
//4. make an array strip and store the point having distance <d from point m
point strip[n];
int j=0;
for(int i=0;i<n;i++)
{
if(abs(p[i].x-m.x)<d)
{
strip[j]=p[i];
j++;
}
}
// calculating smallest distance in strip and finding minimum among d(min of left and right)
// and min dist in strip(min if the closest distance is present in subarray crossing some part of
//left and right sub array)
return minimum(d, stripclosest(strip, j, d, a));
}
float closest(point p[], int n, point a[])
{
//1. sort the points acc to x coordinate
//qsort(p, n, sizeof(point), cmpqx);
sort(p, p+n, cmpx);
return closestutil(p,n, a);
}
int main() {
point p[] = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};
point a[2];
int n = sizeof(p) / sizeof(p[0]);
printf("The smallest distance is %f ", closest(p, n, a));
printpoint(a);
return 0;
}
Binary Indexed Tree - Code in C++
// C++ code to demonstrate operations of Binary Index Tree
#include <iostream>
using namespace std;
int getSum(int BITree[], int n, int index)
{
int sum = 0; // Iniialize result
// index in BITree[] is 1 more than the index in arr[]
index = index + 1;
// Traverse ancestors of BITree[index]
while (index>0)
{
// Add current element of BITree to sum
sum += BITree[index];
// Move index to parent node
index -= index & (-index);
}
return sum;
}
// Updates a node in Binary Index Tree (BITree) at given index
// in BITree. The given value 'val' is added to BITree[i] and
// all of its ancestors in tree.
void updateBIT(int *BITree, int n, int index, int val)
{
// index in BITree[] is 1 more than the index in arr[]
index = index + 1;
// Traverse all ancestors and add 'val'
while (index <= n)
{
// Add 'val' to current node of BI Tree
BITree[index] += val;
// Update index to that of parent
index += index & (-index);
}
}
// Constructs and returns a Binary Indexed Tree for given
// array of size n.
int *constructBITree(int arr[], int n)
{
// Create and initialize BITree[] as 0
int *BITree = new int[n+1];
for (int i=1; i<=n; i++)
BITree[i] = 0;
// Store the actual values in BITree[] using update()
for (int i=0; i<n; i++)
updateBIT(BITree, n, i, arr[i]);
return BITree;
}
// Driver program to test above functions
int main()
{
int *freq,n;
cout<<"enter number of elements: ";
cin>>n;
freq = new int[n];
cout<<"enter the array elements : \n";
for(int i=0;i<n;i++)
cin>>freq[i]; //check on this to validate above figure {3,5,1,6,7,2,3,4,1,9,13,8};
int *BITree = constructBITree(freq, n);
//for(int i=1;i<=n;i++)cout<<BITree[i]<<" "; //uncomment this line to content of BITree[]
cout << "Sum of elements in arr[0..5] is "
<< getSum(BITree, n, 5);
// Let use test the update operation
int id,value;
cout<<"\nenter index and value to be updated : ";
cin>>id>>value;
updateBIT(BITree, n, id, value); //Update BIT for above change in arr[]
cout << "\nSum of elements in arr[0..5] after update is "
<< getSum(BITree, n, 5);
return 0;
}
Binary Indexed Tree ( Fenwick Tree) -Understanding the concept
BINARY
INDEXED TREE (Fenwick tree)
MOTIVATION
Let us consider an array
arr[0 . . . n-1]. With following two task to perform :-
1. Find the sum of first i elements.
2. Change value of a specified element
of the array arr[i] = x where 0 <= i <= n-1.
·
A simple
solution is to
run a loop from 0 to i-1 and calculate sum of elements. To update a value,
simply do arr[i] = x. The first operation takes O(n) time and second operation
takes O(1) time.
·
Or, Create another array and store sum from start to
i at the i’th index in this array. Sum of a given range can now be calculated
in O(1) time, but update operation takes O(n) time now.
Now the
question arises can we perform both operation in O(log n) time ?
One can think
about segment tree but implementation
using segment tree can be complex and require more memory.so better solution
can be produced using binary indexed tree.
Complexities:
·
Time
complexity of construction O(nlogn).
·
Time
complexity of sum and update operation is O(logn).
·
Space
complexity is O(n).
Representation
Binary
Indexed Tree is represented as an array. Let the array be BITree[]. Each node
of Binary Indexed Tree stores sum of some elements of given array. Size of
Binary Indexed Tree is equal to n where n is size of input array. In the below code,
we have used size as n+1 for ease of implementation (where 0th
indexed is used as a dummy node).initialized all the element of BITree[]={0}.
Operations
1. Sum(index) : Returns sum of
arr[0..index]
2. update(index, val): Updates BIT for
operation arr[index] += val
Algorithms
1. Sum(index)
1.1. Initialize sum as 0 and index as index+1.
1.2. while index is greater than zero .
1.2.1. Add
BITree[index] to sum
1.2.2. Go
to parent of BITree[index]. Parent can
be obtained by removing
the last set bit from index, i.e., index =
index - (index & (-index))
1.3. Return sum
2. Update(index, val)
2.1. Initialize index as index+1.
2.2. while index is smaller than or equal
to n.
2.2.1.
Add
value to BITree[index]
2.2.2.
Go
to parent of BITree[index]. Parent can
be obtained
by adding the decimal value of last set bit from index,
i.e., index = index + (index &
(-index))
[Note
above formula adds decimal value corresponding to last set bit]
Subscribe to:
Posts (Atom)