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";

}

}

Program 9TH in C++

PROBLEM STATEMENT :

Give an array of integers, which are in repeated format except one integer, write a function to return that integer

example

[2,2,3,3,4,4,4,5,5] = 4
[2,2,2,3,3,3,3,4,4,4] = 3

SOLUTION:

#include <iostream.h>

#include <cstdio>

using namespace std;

void check(int str[],int size)

{

int i=0;

int count=1;

int count1=1;

//for counting the length of first string pattern

while(i < size)

{

if(str[i] == str[i+1])

{

count++;

i++;

}

else

{

break;

}

}

i++;

//for the length of second string pattern whose length is not equal to length of first string pattern

while(i < size-1)

{

if(str[i] == str[i+1])

{

count1++;

i++;

}

else

{

if(count1 == count)

{

count1=1;

i++;

}

else

{

break;

}

}

}

i++;

//if the common length is equal to first string length found then odd pattern's character is at i-1

if(i == size || str[i] == str[i+count-1])

{

cout<<"\n\nOutput is : "<<str[i-1];

}

//else the common length is equal to second pattern length and hence the odd pattern starts at index 0

else

{

cout<<"\n\nOutput is : "<<str[0];

}

}

int main()

{

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

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

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

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

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

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

}

Program 8TH in C++

PROBLEM STATEMENT :

You are given a url in a format:
<protocol>://<hostname>:<port>/<filename>
eg. http://www.amazon.com/index.html
implement a function which takes url and do following operations on it:-
1. convert protocol & host name to lowercase.
2. If Url don't contain protocol ,then add http:// at the beginning of the url.
3. replace "//" by "/"
4. if Url contain file name, then remove the file name from the Url.

SOLUTION :

Assumption : The string is entered in proper format.

Character strings can be excluded but if entered, proper syntax is followed.

#include <iostream.h>

#include <cstdio>

#include <string.h>

#include <cstdlib>

using namespace std;

string convertUrl( string s)

{

int i=0;

int j=0;

string protocol="";

//Extracting protocol if present

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

{

if(s[i] == ':')

{

if(s[i+1] == '/' && s[i+2] == '/')

{

protocol=s.substr(0,i+3);

j=i;

i+=3;

break;

}

}

}

//if protocol not present, then j=0, and hence i is set to 0 again.

if( j ==0)

{

i=0;

}

//Changing the case of host name to lower chars if in upper

while( s[i] != '/' && s[i] != '\0' && s[i] != ':')

{

if(s[i] >= 65 && s[i] <= 90)

{

s[i] += 32;

}

i++;

}

//moving from port portin to filename or end of string

if(s[i] == ':')

{

while( s[i] != '/' && s[i] != '\0')

{

i++;

}

}

//at the last slash, if present, filename is extracted out and s is set to string before that only.

if(s[i] == '/')

{

s=s.substr(0,i);

}

//entering protocol if not entered or not correct

if(protocol == "" && protocol != "http://" && protocol != "https://")

{

protocol="http://";

}

// removing one slash from protocol

if(protocol[protocol.length()-1] == '/' && protocol[protocol.length()-2] == '/')

{

protocol[protocol.length()-1]='\0';

}

//Changing protocol part to lower case

for( i=0; i < protocol.length(); i++)

{

if(protocol[i] >=65 && protocol[i]<=90)

{

protocol[i]+=32;

}

}

//merging the two strings on the basis of protocol already present or not

if(j!=0)

{

protocol += s.substr((j+3),s.length());

}

else

{

protocol += s.substr(j,s.length());

}

return protocol;

}

int main()

{

string url;

cout<<"\n\nEnter URL : ";

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

cin.clear();

url=convertUrl(url);

cout<<"\n\nThe formatted URL is : "<<url<<endl<<endl;

}

Program 7TH in C++

PROBLEM STATEMENT :

WAP to print the nodes of a tree in a each separate line.

SOLUTION

#include <iostream.h>

#include <cstdio>

#include <vector.h>

#include <unistd.h>

#include <queue.h>

using namespace std;

struct node

{

int data;

vector<node*> children;

};

//receiving input with error check

int input()

{

int num;

while(true)

{

cout<<"\n\nEnter : ";

cin>>num;

if(cin.good())

{

return num;

}

else

{

cout<<"\n\nYou Entered a non integral value\n\n";

cin.clear();

cin.ignore(numeric_limits<streamsize>::max(),'\n');

continue;

}

}

}

//for arranging childs to their parents

void create(node* Node, int num1)

{

int i=0,y=0;

int num=num1;

int val;

int curr=1;

int flag=0;

for(y=0; y < num; y++)

{

if(curr < num)

{

cout<<"\n\nEnter No of children for node " << y<<" :";

val=input();

while(val > 0)

{

Node[y].children.push_back(&Node[curr++]);

val--;

}

}

else

{

flag=1;

break;

}

}

}

//printing tree in the required form

void printtree(node * root)

{

queue<node*> q;

int curr_lev_counter,next_lev_counter;

q.push(root);

curr_lev_counter=1;

next_lev_counter=0;

while(!q.empty())

{

node * nd = q.front();

q.pop();

curr_lev_counter--;

cout<data<<" ";

for(int i=0; i < nd->children.size(); i++)

{

q.push(nd->children[i]);

next_lev_counter++;

}

if(curr_lev_counter == 0)

{

curr_lev_counter=next_lev_counter;

next_lev_counter=0;

cout<<endl;

}

}

}

int main()

{

int num;

int i=0;

cout<<"\n\nHow many nodes you want to enter in the tree : ";

num=input();

if(num > 0)

{

node Node[num];

cout<<"\n\n Enter Values of nodes \n\n";

for( i=0; i < num; i++)

{

Node[i].data = input();

}

create(Node,num);

cout<<"\n\nThe tree looks like : \n\n";

printtree(Node);

cout<<endl<<endl;

}

else

{

cout<<"\n\nThe tree is empty\n\n ";

}

}