Program 15TH in C++ (VERSION 2)

PROBLEM STATEMENT :

Matrix with rows and column sorted. Find a particular element.

NOTE:

Works for arrays where the last element of previous row in 2d matrix is less than first element of next row with time complexity l0g m +log n

SOLUTION :

#include <iostream.h>

#include <cstdio>

using namespace std;

void find(int arr[][4], int m, int n, int target, int &row, int &col)

{

int a1d[16];

int first;

int last;

for(int x=0; x<16; x++)

{

a1d[x]=arr[x/m][x%n];

}

first=0;

last=15;

while(first>=0 && last<16 && first <= last)

{

int mid = (first+last)/2;

if(a1d[mid]==target)

{

row=mid/m;

col=mid%n;

return;

}

else if(a1d[mid] > target)

{

last=mid-1;

}

else

{

first=mid+1;

}

}

}

int main()

{

int a2d[4][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};

int val;

cout<<"\n\nEnter the element you want to find : ";

cin>>val;

int row = -1;

int col = -1;

find(a2d,4,4,val,row,col);

if(row !=-1 && col !=-1)

{

cout<<"\n\nElement is at row : "<<row <<" and column : "<<col<<endl;

}

else

{

cout<<"\n\nElement not present in the array\n\n";

}

}

Program 15TH in C++ (VERSION 1)

PROBLEM STATEMENT :

Matrix with rows and column sorted. Find a particular element.

NOTE:

It works for all kind of arrays with O(m+n) time complexity.

SOLUTION:

#include <iostream.h>

#include <cstdio>

using namespace std;

void find(int a2d[][4], int m, int n, int target)

{

int i=0;

int j=n-1;

int flag=1;

while(i>=0 && i<m && j >=0 && j<n)

{

if(a2d[i][j]==target)

{

flag=0;

cout<<"Element "<<target << "exists at " << " row : "<<i<<" and column : "<<j<<endl<<endl;

j--;

}

else if(a2d[i][j] > target)

{

j--;

}

else

{

i++;

}

}

if(flag == 1)

{

cout<<"\n\n Element is not found in the given array \n\n";

}

}

int main()

{

int row=0;

int col=0;

int a2d[][4]={{1,2,3,5},{2,5,6,7},{3,6,11,13},{4,10,15,18}};

find(a2d,4,4,6);

}

Program 14TH in C++

PROBLEM STATEMENT :

there two article:A ,B,which is very large. get three or more successive words in A,to find if it appears in B ,and count the times. For example , 'book' 'his' 'her' appear in A ,how many times it appears in B?

SOLUTION:

#include <iostream.h>

#include <cstdio>

#include <map.h>

#include <string.h>

using namespace std;

void findArr(string a, string out[])

{

string s="";

int j=0;

for(int i=0; i<=a.length(); i++)

{

if(a[i]!=' ' && a[i]!='\0')

{

s+=a[i];

}

else

{

out[j]=s+'\0';

j++;

s="";

}

}

}

int size( string a)

{

int count =0;

for(int i=0; i

{

if(a[i] == ' ')

count++;

}

return count+1;

}

int main()

{

string a="hello bye tea coffee";

string b="hello hello tea";

string arr1[size(a)];

string arr2[size(b)];

findArr(a,arr1);

findArr(b,arr2);

map<string,int> store;

for(int i=0; i<sizeof(arr1)/sizeof(string); i++)

{

store.insert(pair(arr1[i],0));

}

map<string,int> :: iterator it;

for(int i=0; i

{

it=store.find(arr2[i]);

if(it!=store.end())

{

store[arr2[i]]+=1;

}

}

for(int i=0; i<sizeof(arr1)/sizeof(string); i++)

{

cout<<"\nString "<<arr1[i] << " occurs in B " << store[arr1[i]] << " number of times"<< endl;

}

}

Program 13TH in C++

PROBLEM STATEMENT :

Return true if two trees are same

SOLUTION:

#include <iostream.h>

#include <cstdio>

#include <queue.h>

#include <vector.h>

using namespace std;

struct node

{

int data;

vector<node*> children;

};

//checking by level order traversal

bool check_tree(node* n, node* m)

{

queue<node*> q1;

queue<node*> q2;

int curr_count=1;

int next_count=0;

q1.push(n);

q2.push(m);

while(!q1.empty() && !q2.empty())

{

node* val1=q1.front();

node* val2=q2.front();

q1.pop();

q2.pop();

curr_count--;

if(val1->data == val2->data)

{

int size1=val1->children.size();

if(size1 == val2->children.size())

{

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

{

q1.push(val1->children[i]);

q2.push(val2->children[i]);

next_count++;

}

if(curr_count == 0)

{

curr_count=next_count;

next_count=0;

}

}

else

{

return false;

}

}

else

{

return false;

}

}

return true;

}

int main()

{

node Node[10];

node Node1[10];

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

{

Node[i].data=i*2;

Node1[i].data=i*2;

}

//arranging childrens in first tree

Node[0].children.push_back(&Node[1]);

Node[0].children.push_back(&Node[2]);

Node[1].children.push_back(&Node[3]);

Node[1].children.push_back(&Node[4]);

Node[1].children.push_back(&Node[5]);

Node[2].children.push_back(&Node[6]);

Node[2].children.push_back(&Node[7]);

Node[2].children.push_back(&Node[8]);

Node[3].children.push_back(&Node[9]);

//arranging children in second tree

Node1[0].children.push_back(&Node1[1]);

Node1[0].children.push_back(&Node1[2]);

Node1[1].children.push_back(&Node1[3]);

Node1[1].children.push_back(&Node1[4]);

Node1[1].children.push_back(&Node1[5]);

Node1[2].children.push_back(&Node1[6]);

Node1[2].children.push_back(&Node1[7]);

Node1[3].children.push_back(&Node1[8]);

Node1[3].children.push_back(&Node1[9]);

bool out=check_tree(Node,Node1);

if(out == true)

cout<<"\n\n Trees are same\n\n";

else

cout<<"\n\n Trees are not same\n\n";

}

Program 12TH in C++

PROBLEM STATEMENT :

An array has duplicate elements each elements occurs even number of time except one occurs odd number of times. Print that number. Provide the complexites of the solution

NOTE:

1) Works for pattern only else XOR is the solution.

2)Sort the array and then apply the soltuion

SOLUTION :

#include <iostream.h>

#include <cstdio>

void check(int a[],int size)

{

for(int i=0; i<size-1; i+=2)

{

if(a[i]!=a[i+1])

{

cout<<"\n\nThe odd one is : "<<a[i];

return;

}

}

cout<<"\n\nThe odd one is : "<<a[size-1];

}

int main()

{

int arr1[]={2,2,4,4,4,4,5,5,6};

int arr2[]={2,3,3,3,3,4,4,5,5};

int arr3[]={1,1,1,1,2,2,2,2,2,3,3};

check(arr1,sizeof(arr1)/sizeof(int));

check(arr2,sizeof(arr2)/sizeof(int));

check(arr3,sizeof(arr3)/sizeof(int));

}

Program 11TH in C++

PROBLEM STATEMENT :

input linked list is : 1->9->3->8->5->7->7

do you see any pattern in this input ?
odd placed nodes are in increasing order and even placed nodes are in decreasing order.
write a code that gives the the following linkedlist:
output linked list should be 1->3->5->7->7->8->9

?? can it be done inplace ?

SOLUTION :

#include <iostream.h>

#include <cstdio>

#include <list.h>

using namespace std;

void print(int arr[], int size)

{

list<int> li(arr,arr+size);

list<int> :: iterator it;

list<int> li1;

list<int> :: reverse_iterator it1;

cout<

//storing odd no elements in the new list and deleting the same from old list

for(it=li.begin(); it!=li.end(); it++)

{

li1.push_back(*it);

it=li.erase(it);

if(it!=li.end())

{

continue;

}

else

{

break;

}

}

//old list now contain the even places elements only and adding them from back to front in new list created above

for(it1=li.rbegin(); it1!=li.rend(); )

{

li1.push_back(*it1);

li.remove(*it1);

}

//displaying newly created list

for(it=li1.begin(); it!=li1.end(); it++)

{

cout<<*it<<" ";

}

}

int main()

{

int arr[]={1,9,3,8,5,7,7};

int arr1[]={1,9,4,6,7,3};

int arr2[]={2,5,6,4,9,3};

print(arr,sizeof(arr)/sizeof(int));

print(arr1,sizeof(arr1)/sizeof(int));

print(arr2,sizeof(arr2)/sizeof(int));

}

Program 10TH in C++

PROBLEM STATEMENT :

Write an efficient code to print pairs of anagrams from a given set of strings.

ex: anna, hjsds, nana, werwe, sads, eerww

Ouput:
anna nana
werwe eerww

SOLUTION :

#include <iostream.h>

#include <cstdio>

#include <vector.h>

#include <map.h>

#include <string.h>

#include <unistd.h>

using namespace std;

//bubble sort to sort strings

string sorting(string s)

{

char temp;

for(int i=0; i < s.length()-1; i++)

{

for(int j=i+1 ; j

{

if(s[i] > s[j])

{

temp = s[i];

s[i]=s[j];

s[j]=temp;

}

}

}

return s;

}

int main()

{

vector<string> v;

multimap<string,string> store;

multimap<string,string> :: iterator itm;

multimap<string,string> :: iterator itm1;

string s;

string sorted;

int i=0;

int flag=0;

//pushing strings input by user in vector

while(true)

{

getline(cin,s,'\n');

if(cin.good())

v.push_back(s);

else

break;

}

//storing sorted string as key and value as original string in multimap

for(i=0; i<v.size(); i++)

{

sorted=sorting(v[i]);

store.insert(pair<string,string>(sorted,v[i]));

}

pair<multimap<string,string>::iterator,multimap<string,string>::iterator> ret;

//traversing the map to print the pairs of anagrams if present

for(itm1=store.begin(); itm1!=store.end(); itm1++)

{

ret=store.equal_range(itm1->first);

if((int)store.count(itm1->first) != 1)

{

if(flag == 0)

{

cout<<"\n\nAnagrams are as follows :\n\n";

flag=1;

}

for(itm=ret.first; itm!=ret.second; itm++)

{

cout<<itm->second<<" ";

store.erase(itm);

}

cout<<endl<<endl;

}

}

if(flag == 0)

{

cout<<"\n\nNo Anagrams are present\n\n";

}

}