skum
BAN USERclass tree* temp = NULL;
void makeTree(class tree** root, int arr[], int start, int end)
{
if(start<=end)
{
int mid = start + (end-start)/2;
*root = new tree(arr[mid]);
if(!temp)
temp = *root;
makeTree(&(*root)->left, arr, start, mid-1);
makeTree(&(*root)->right, arr, mid+1, end);
}
}
void function1(int arr[], int start, int end, int data[], int startD, int endD)
{
if(start<=end+1)
{
if(startD==endD+1)
{
int mul = 1;
for(int i=0;i<=endD;i++)
{
// cout<<" "<<data[i];
mul *= data[i];
}
cout<<" "<<mul<<endl;
return;
}
data[startD] = arr[start];
function1(arr, start+1, end, data, startD+1, endD);
function1(arr, start+1, end, data, startD, endD);
}
}
void function(int arr[], int size)
{
for(int i=0;i<=size;i++)
{
int *data = new int[i+1];
//cout<<" spot 1 "<<i<<endl;
function1(arr, 0, size, data, 0, i);
delete[] data;
}
}
bool check = true;
bool isPalindrome(string str, int start, int end)
{
if(start<end)
{
while(start<=end && !((str[start] >= 'a' && str[start] <= 'z') || (str[start] >= 'A' && str[start] <= 'Z')))
start++;
while(end >=0 && !((str[end] >= 'a' && str[end] <= 'z') || (str[end] >= 'A' && str[end] <= 'Z')))
end--;
if(toupper(str[start]) != toupper(str[end]))
{
check = false;
return false;
}
return check && isPalindrome(str, start+1, end-1);
}
return true;
}
void squareRoot(double num, double start, double end, double& value)
{
if(!value)
{
if(num==1)
{
value = 1;
return;
}
else if(num==4)
{
value = 2;
return;
}
double mid = (start+end)/2;
if(mid*mid == num)
{
value = mid;
return;
}
else if(mid*mid > num)
end = mid;
else
start = mid;
squareRoot(num, start, end, value);
}
}
Will add more code to handle decimal cases.
- skum July 27, 2015void reverseEachWord(string& str, int start, int end)
{
while(start<end)
{
swap(str[start++], str[end--]);
}
}
void reverseWord(string& str)
{
int len = str.length();
int start = 0, end = 0;
for(int i=0;i<len;i++)
{
start = i;
end = i;
while(i< len && str[i] != ' ')
{
end++;
i++;
}
reverseEachWord(str, start, end-1);
if(str[i] == ' ')
continue;
}
}
void function(string str, int& start, int& end)
{
int hash[26] = {-1};
for(int i=0;i<25;i++)
hash[i] = -1;
int left = 0, right = 0;
hash[str[0]-97] = 0;
for(int i=1;i<str.length();i++)
{
if(hash[str[i]-97] != -1 && hash[str[i]-97] >= left)
{
left = hash[str[i]-97]+1;
right = i;
}
else
right++;
hash[str[i]-97] = i;
if(right-left+1 >= end-start+1)
{
start = left;
end = right;
}
}
}
bool function(string src, string dst)
{
bool hash[26] = {false};
for(int i=0;i<src.length();i++)
hash[(int)src[i]-97] = true;
int count = src.length();
for(int i=0;i<dst.length();i++)
{
if(!count)
return true;
if(hash[(int)dst[i]-97])
{
count--;
continue;
}
else
count = src.length();
}
return false;
}
/*
Sparse number is an integer if there are no adjacent 1 in it's binary representation.
Like: 5 -> 101 (no adjacent 1)
9 -> 1001 (no adjacent 1)
while 6-> 110 is not sparse number.
Now you are given an integer find the NEXT BIGGER sparse number.Please mind 'it is next bigger'.
*/
#include<iostream>
using namespace std;
int countBits(int num)
{
if(num)
{
return 1+countBits(num>>1);
}
return 0;
}
int getPosition(int num, int count)
{
int temp = num;
for(int i=0;i<count-1;i++)
{
if(!((temp>>i) & 1) && !((temp>>(i+1))&1))
return i;
}
return -1;
}
int function(int num)
{
int n = countBits(num);
int pos = getPosition(num, n);
if(pos == -1)
return num<<1;
else if(!pos)
return num | 1;
else
{
int num1 = (num >> pos)<<pos;
int num2 = (num & ((2<<pos)-1))<<1;
return (num1 | num2);
}
}
int main()
{
int num;
cout<<" Enter number :- ";
cin>>num;
int sparse = function(num);
cout<<" Sparse Number is :- "<<sparse<<endl;
system("PAUSE");
return 0;
}
Here's a hash based solution for this problem.
Create a structure
struct node
{
int* address;
bool visited;
struct node* next;
};
1. Create an array of 26 (alphabatic characters) node.
2. For each entry in linked list fill the hash table (based on starting character).
2.1. address - pointer to for linked list node.
2.2. visited = false
2.3. next = NULL (it will come into use when two nodes have same starting character, using the idea of chaining concept in hashing)
Now lets try to fill the given linked list in hash table:-
Pointer Value :- 0x100 0x200 0x300 0x400 0x500 0x600 0x700
Linked List :- here -> is -> ew -> long -> shut -> error -> roll
Once these pointer values are feeded into the nodes we are done with the hash table.
Now, to find the possibilities we start from first node of linked list. Let's do it one by one.
1. a. Here (search for h in hash table).
b. Since 'e' is last character of here, now search hash table for 'e'. Now we have two enteries for 'e' we will do it one at a time. Lets say we choose "ew" first time, and if we have next of "ew" != NULL, we mark "ew" as visited (i.e. "ew"->visited = true) now we proceed for 'w' and continue same ways.
c. Since after here 'e', there is one more possibility of having "error" 'e', for "ew" we have already visited (since visited flag for "ew" is true), we will go forward in that chain and continue.
In this way we can have all possiblities. Thanx
#include<iostream>
using namespace std;
void function1(int arr[], int start, int end, int data[], int startD, int endD, bool& done)
{
if(start<=end+1)
{
if(startD == endD && !done)
{
int maxV = -10000, minV = INT_MAX;
for(int i=0;i<endD;i++)
{
if(data[i] > maxV)
maxV = data[i];
if(data[i] < minV)
minV = data[i];
}
if(maxV-minV == 1)
{
cout<<"Output :-";
for(int i=0;i<endD;i++)
{
cout<<" "<<data[i];
}
done = true;
cout<<endl;
}
}
data[startD] = arr[start];
function1(arr, start+1, end, data, startD+1, endD, done);
function1(arr, start+1, end, data, startD, endD, done);
}
}
void function(int arr[], int size)
{
int data[size];
bool done = false;
for(int i=size;i>=2 && !done;i--)
function1(arr, 0, size, data, 0, i, done);
}
int main()
{
int arr[] = {6, 10, 6, 7, 8, 9, 0};
int size = sizeof(arr)/sizeof(*arr);
function(arr, size-1);
cout<<endl;
system("PAUSE");
return 0;
}
#include<iostream>
#include<limits>
using namespace std;
int absl(int a, int b)
{
return a>b?(a-b):(b-a);
}
void getMin(int a, int b, int c, int& inc)
{
int minV = a<b?a:b;
minV = c>minV?minV:c;
if(minV == a) inc = 1;
else if(minV == b) inc = 2;
else inc = 3;
}
void function(int arr[], int alen, int brr[], int blen, int crr[], int clen, int& a, int& b, int& c)
{
int i=0, j=0, k=0, inc=0, minV, ans = INT_MAX, prev;
while(i<=alen || j<=blen || k<=clen)
{
inc = 0;
prev = ans;
ans = min(ans, absl(arr[i], brr[j]) + absl(crr[k], brr[j]) + absl(arr[i], crr[k]));
if(prev!=ans)
{
a = arr[i];
b = brr[j];
c = crr[k];
}
if(i==alen && j == blen && k == clen) break;
else if(i==alen && c==alen) inc = 2;
else if(j==blen && k==clen) inc = 1;
else if(i==alen && j==blen) inc = 3;
else getMin(arr[i], brr[j], crr[k], inc);
if(inc == 1) i++;
else if(inc == 2) j++;
else if(inc ==3) k++;
}
}
int main()
{
int arr[] = {2, 3, 4, 6, 7, 9};
int brr[] = {0, 1, 5, 7, 8, 14};
int crr[] = {11, 12, 13, 14, 17, 23};
int alen = sizeof(arr)/sizeof(*arr);
int blen = sizeof(brr)/sizeof(*brr);
int clen = sizeof(crr)/sizeof(*crr);
int a = 0, b = 0, c = 0;
function(arr, alen, brr, blen, crr, clen, a, b, c);
cout<<" a = "<<a<<" b = "<<b<<" c = "<<c<<endl;
system("PAUSE");
return 0;
}
#include<iostream>
#include<string>
using namespace std;
void function(string str, int count)
{
if(count<0)
return;
else if(count==0)
return;
else
{
int len = str.length();
for(int i=0;i<len-1-count;i++)
{
cout<<str[0];
for(int j=0;j<i;j++)
cout<<str[1+j];
cout<<count;
for(int j=count+1+i;j<len-1;j++)
cout<<str[j];
cout<<str[len-1];
cout<<" ";
}
cout<<endl<<endl;
if(count>=0)
function(str, count-1);
}
}
int main()
{
string str = "careercup";
function(str, str.length()-2);
system("PAUSE");
return 0;
}
/*
Consider an array of integers wherein each element is +1 or -1 its preceding element.
Given a number, find the first occurence of this number (index) in this array without using linear search.
For example, consider the array :
4 5 6 5 6 7 8 9 10 9 10 (each element in this array is +1 or -1 its preceding element)
Input : 10 (find first occurence of 10 without using linear search)
Output : 8
*/
#include<iostream>
using namespace std;
void function(int arr[], int start, int end, int num, int& loc)
{
if(loc == -1 && start<=end)
{
if(start==end && arr[start] == num)
{
loc = start;
return;
}
else if(start == end)
return;
else if(start+1 == end)
{
if(arr[start] == num)
{
loc = start;
return;
}
else if(arr[end] == num)
{
loc = end;
return;
}
}
int mid = (start+end)/2;
function(arr, start, mid, num, loc);
function(arr, mid+1, end, num, loc);
}
}
int main()
{
int arr[] = {7, 6, 5, 4, 5, 6, 5, 6, 7, 8, 5};
int size = sizeof(arr)/sizeof(*arr);
int loc = -1;
int num;
cout<<" Enter number to be found :- ";
cin>>num;
function(arr, 0, size-1, num, loc);
cout<<" First location of "<<num<<" is :- "<<loc<<endl;;
system("PAUSE");
return 0;
}
/*
One unsorted array is given.Find out the index i and j ,j> i for which
a[j] - a[i] is maximum.perform in linear time complexity.
*/
#include<iostream>
using namespace std;
int main()
{
int arr[] = {1, 12, 3, 6, 2, 8, 17, 9, 1};
// int arr[] = {7, 5, 2};
int size = sizeof(arr)/sizeof(*arr);
int tillMin = arr[0];
int tillMax = arr[1];
int diff = tillMax-tillMin;
int valI=0, valJ = 1;
for(int i=2;i<size;i++)
{
if(diff < arr[i]-tillMin)
diff = arr[i]-tillMin;
if(arr[i] > tillMax)
{
valJ = i;
tillMax = arr[i];
}
else if(arr[i] < tillMin)
{
valI = i;
tillMin = arr[i];
}
}
cout<<" Maximum difference is :- "<<diff<<" i = "<<valI<<" j = "<<valJ<<endl;
system("PAUSE");
return 0;
}
/*
One unsorted array is given.Find out the index i and j ,j> i for which
a[j] - a[i] is maximum.perform in linear time complexity.
*/
#include<iostream>
using namespace std;
int main()
{
int arr[] = {1, 12, 3, 6, 2, 8, 17, 9, 1};
// int arr[] = {7, 5, 2};
int size = sizeof(arr)/sizeof(*arr);
int tillMin = arr[0];
int tillMax = arr[1];
int diff = tillMax-tillMin;
int valI=0, valJ = 1;
for(int i=2;i<size;i++)
{
if(diff < arr[i]-tillMin)
diff = arr[i]-tillMin;
if(arr[i] > tillMax)
{
valJ = i;
tillMax = arr[i];
}
else if(arr[i] < tillMin)
{
valI = i;
tillMin = arr[i];
}
}
cout<<" Maximum difference is :- "<<diff<<" i = "<<valI<<" j = "<<valJ<<endl;
system("PAUSE");
return 0;
}
void function(int arr[], int size)
{
int maxGlobal = arr[0];
int maxCurrent = arr[0];
int start = 0, end = 0, prevEnd = 0, prevMax = 0;
for(int i=1;i<=size;i++)
{
if(arr[i] > arr[i]+maxCurrent)
{
start = i;
end = i;
maxCurrent = arr[i];
}
else
{
maxCurrent = arr[i]+maxCurrent;
end++;
if(prevMax<maxCurrent)
{
prevMax = maxCurrent;
prevEnd = end;
}
}
maxGlobal = max(maxCurrent, maxGlobal);
}
cout<<" Maximum sum :- "<<maxGlobal<<" start = "<<start<<" prevEnd = "<<prevEnd<<endl;
}
#include<iostream>
using namespace std;
bool isPairWiseSumEqual(int arr[], int start, int end)
{
for(int i=0;i<end;i++)
{
for(int j=i;j<=end;j++)
{
if(arr[i] > arr[j])
swap(arr[i], arr[j]);
}
}
if(arr[0]+arr[end] == arr[1]+arr[end-1])
{
cout<<arr[0]<<" + "<<arr[end]<<" = "<<arr[1]<<" + "<<arr[end-1]<<endl;
return true;
}
return false;
}
int i = 1;
void getFourNumbers(int arr[], int startA, int endA, int data[], int startD, int endD)
{
if(startA<=endA+1)
{
if(startD == endD+1)
{
int temp[endD+1];
for(int i=0;i<=endD;i++)
{
temp[i] = data[i];
}
bool check = isPairWiseSumEqual(temp, 0, endD);
i++;
return;
}
data[startD] = arr[startA];
getFourNumbers(arr, startA+1, endA, data, startD+1, endD);
getFourNumbers(arr, startA+1, endA, data, startD, endD);
}
}
void function(int arr[], int size)
{
int data[4];
getFourNumbers(arr, 0, size, data, 0, 3);
}
int main()
{
int arr[] = {3,4,7,1,2,9,8};
int size = sizeof(arr)/sizeof(*arr);
function(arr, size-1);
cout<<endl;
system("PAUSE");
return 0;
}
void function(string& str)
{
int pos = 0;
for(int i=0;i<str.length()-1;i++)
{
if(str[i] == 'b')
continue;
else if(str[i] == 'a' && str[i+1] == 'c')
{
i += 1;
continue;
}
if(i < str.length()-1)
str[pos++] = str[i];
}
if(!(str[str.length()-1] != 'b' || (str[str.length()-2] != 'a' && str[str.length()-1] != 'c')))
str[pos++] = str[str.length()-1];
for(int i=0;i<pos;i++)
cout<<str[i];
cout<<endl;
}
Here is my approach :-
1. Sort array according to the first digit of each number
(for given input, it should be - 94, 9, 4, 1, 14, keeping order is not necessary)
2. Now run a loop from i=0 to n-1 elements , pick pair each time (like 0, 1 then 1, 2....)
if(no. of digits of a and b are equal)
continue
else // formNum(a, b) - form a number eg, formNum(74, 23) - 7423
if(formNum(a, b) < formNum(b, a)
swap(a, b);
Now just print that array, we get the largest number.
Here's the code
/*
Given an integer array, sort the integer array such that the concatenated
integer of the result array is max. e.g. [4, 94, 9, 14, 1] will be sorted
to [9,94,4,14,1] where the result integer is 9944141
*/
#include<iostream>
using namespace std;
int digits(int num)
{
if(!num)
return 0;
int count = 0;
while(num)
{
num /= 10;
count++;
}
return count;
}
int formNum(int a, int b)
{
int digA = digits(a);
int digB = digits(b);
int factor = 1;
for(int i=0;i<digB;i++)
factor = 10*factor;
return (a*factor + b);
}
int MSB(int num)
{
if(num<=9)
return num;
else
{
while(num>=10)
num /= 10;
}
return num;
}
void function(int arr[], int size)
{
for(int i=0;i<size;i++)
{
for(int j=i+1;j<=size;j++)
{
if(MSB(arr[i]) < MSB(arr[j]))
swap(arr[i], arr[j]);
}
}
for(int i=0;i<size;i++)
{
if(digits(arr[i]) == digits(arr[i+1]))
continue;
else
{
if(formNum(arr[i], arr[i+1]) < formNum(arr[i+1], arr[i]))
swap(arr[i], arr[i+1]);
}
}
cout<<" Number is :- ";
for(int i=0;i<=size;i++)
cout<<arr[i];
cout<<endl;
}
int main()
{
int arr[] = {9,99,91,5,59,8,81,4,44,21};
int size = sizeof(arr)/sizeof(*arr);
function(arr, size-1);
system("PAUSE");
return 0;
}
Please comment on the approach. I know, i get the right answer but i just want your comments on approach.
- skum July 06, 2015I can think of this only.
Complexity-Horrible.
#include<iostream>
using namespace std;
void function(int arr[], int st, int size, int data[], int start, int end)
{
if(st <= size)
{
if(start==end)
{
int sum = 0;
for(int i=0;i<end;i++)
sum += data[i];
if(!sum)
{
for(int i=0;i<end;i++)
cout<<" "<<data[i];
cout<<endl;
}
return;
}
data[start] = arr[st];
function(arr, st+1, size, data, start+1, end);
function(arr, st+1, size, data, start, end);
}
}
int main()
{
int arr[] = {1,2,3,-2,-1,4,-5,1};
int size = sizeof(arr)/sizeof(*arr);
for(int i=1;i<=size;i++)
{
int* data = new int[i];
function(arr, 0, size-1, data, 0, i);
}
system("PAUSE");
return 0;
}
bool checkRedundancy(string str)
{
int len = str.length();
stack<char> st;
int optr = 0;
for(int i=0;i<len;i++)
{
if(str[i] == '(')
st.push(')');
else if(str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/')
optr++;
else if(str[i] == ')')
{
if(!optr)
return true;
optr--;
st.pop();
}
}
if(!st.empty() && !optr)
return true;
return false;
}
1. Take a variable to keep track of number of operator, initialize to 0 (optr).
2. Keep pushing "(".
3. If operator found, increment it.
4. If ")" found, pop once from stack and decrement optr by 1.
5. Keep doing this till end of input.
6. For no redundancy stack should be empty with optr = 0.
Hope it explains.
class tree* newRoot = NULL;
class tree* prev = NULL;
void modifyTree(class tree* root)
{
if(root)
{
modifyTree(root->left);
if(!newRoot)
{
newRoot = root;
prev = root;
}
if(root && prev && root != prev)
{
prev->right = root;
root->left = NULL;
prev = root;
}
modifyTree(root->right);
}
}
class tree* prev = NULL;
class tree* newRoot = NULL;
void convertTree(class tree* root)
{
if(root)
{
prev = root;
newRoot = prev;
convertTree(root->left);
}
if(prev && root && prev != root)
{
prev->left = root->right;
prev->right = root;
root->left = NULL;
prev = root;
}
}
int search(string src, int s, char ch)
{
for(int i=s;i<src.length();i++)
{
if(src[i] == ch)
return i;
}
return -1;
}
void pathSrc2Dst(string src, string dst)
{
int lenS = src.length();
int lenD = dst.length();
if(lenS != lenD)
{
cout<<" Invalid Input "<<endl;
return;
}
int d = 0, s = 0;
cout<<" "<<src;
while(true)
{
int loc = search(src, s, dst[d]);
if(loc<0)
{
cout<<" Invalid Input "<<endl;
return;
}
for(int i=loc;i>s;i--)
swap(src[i], src[i-1]);
s++;
d++;
cout<<" ----> "<<src;
if(s == src.length() || src == dst)
break;
}
cout<<endl;
}
int main()
{
string src, dst;
cout<<" Enter source :- ";
cin>>src;
cout<<" Enter destination :- ";
cin>>dst;
pathSrc2Dst(src, dst);
return 0;
}
#include<iostream>
using namespace std;
bool isSquare(int num, int& whose)
{
int i=2;
if(num==1)
{
whose = 1;
return true;
}
while(true)
{
if(i*i == num)
{
whose = i;
return true;
}
else if(i*i > num)
{
return false;
}
i++;
}
}
int main()
{
int num;
cout<<" Get Number :- ";
cin>>num;
int minTill = num;
int minV = 0;
int count;
int x = 0;
if(isSquare(num, x))
{
minV = 1;
minTill = 1;
}
if(num==3)
{
minV = 3;
minTill = 1;
}
while(minTill > 2)
{
bool check = false;
count = 0;
int diff = num;
int sum = 0;
for(int i=num;i>0;i--)
{
int t = 0;
if(isSquare(i, t))
{
if(minTill == t && check)
{
sum += t*t;
i = num-sum;
diff = diff-t*t;
count++;
}
else if(t==1)
{
count = count+diff;
i = 0;
}
else if(t<minTill)
{
if(!check)
{
minTill = t;
check = true;
}
sum += t*t;
i = num-sum;
diff = diff-t*t;
count++;
}
if(i==4 || i == 1)
{
count++;
i = 0;
}
}
if(i==0)
{
diff = num;
sum = 0;
check = false;
}
}
if(count == 2)
{
minV = 2;
break;
}
if(!minV)
minV = count;
else if(minV > count && !check)
minV = count;
cout<<endl<<endl;
}
cout<<" Result is :- "<<minV<<endl;
return 0;
}
@ 010010.bin sry my bad, i thought input as kinda rotated array like:-
a.....Peak.....b, i took all elemnts right of Peak as smaller than a, which isn't the case.
As far as compilation error, i posted the running code (on DevC++) for gcc, need to comment system("PAUSE") .
To be precise, answer should be "it may work sometime and fail sometime"
Explanation:-
We have two processes P1 and P2, and lock=0;
if (lock) ---- Line 1
wait(); // It's already locked so wait(sleep) till someone wakes me up --- Line2
else ------ Line 3
lock=1; // I locked it ------ Line 4
/* Critical Section - Increment g */
lock = 0; // Lock released, so wakeup only one of other waiting threads, if any
Let's say P1 is scheduled first, and it execute Line1, and context switched with P2, and again P2 executes Line1, now we arrived to the condition where both P1 and P2 see lock as free, and will execute Line4, and as a result there will be deadlock as both will wait for lock to be freed but none would be able to do so.
#include<iostream>
using namespace std;
int getPoint(int arr[], int start, int end, int size)
{
if(start<end)
{
int mid = (start+end)/2;
if(arr[mid] > arr[mid+1] && arr[mid] > arr[mid-1])
return mid;
if(arr[start]<arr[mid] && arr[mid]>arr[end])
return getPoint(arr, mid+1, end, size);
else if(arr[start] > arr[mid] && arr[mid] > arr[end])
return getPoint(arr, start, mid, size);
}
}
int findVal1(int arr[], int start, int end, int val)
{
if(start<=end)
{
int mid = (start+end)/2;
//cout<<" start " <<start<<" mid = "<<mid<<" end = "<<end<<endl;
if(arr[mid]==val)
return mid;
else if(arr[mid] > val)
return findVal1(arr, start, mid-1, val);
else
return findVal1(arr, mid+1, end, val);
}
}
int findVal2(int arr[], int start, int end, int val)
{
if(start<=end)
{
int mid = (start+end)/2;
//cout<<" start " <<start<<" mid = "<<mid<<" end = "<<end<<endl;
if(arr[mid]==val)
return mid;
else if(arr[mid] < val)
return findVal2(arr, start, mid-1, val);
else
return findVal2(arr, mid+1, end, val);
}
}
void function(int arr[], int size, int num, int& val)
{
int pt = getPoint(arr, 0, size, size);
//cout<<" pt = "<<pt<<endl;
if(arr[pt] == num)
val = pt;
else if(pt != size && num > arr[pt+1])
{
//cout<<" spot 1"<<endl;
val = findVal1(arr, 0, pt, num);
}
else
{
//cout<<" spot 2"<<endl;
val = findVal2(arr, pt+1, size, num);
}
//cout<<" Point is :- "<<val<<endl;
}
int main()
{ // 0 1 2 3 4 5 6 7 8 9 10 11
int arr[] = {8, 9, 10, 12, 16, 18, 19, 21, 4, 3, 2, -1};
int size = sizeof(arr)/sizeof(*arr);
cout<<" Enter value to find :- ";
int num;
cin>>num;
int val = -1;
function(arr, size-1, num, val);
if(val>=0)
cout<<" Result is :- "<<val;
else
cout<<" Not Found "<<endl;
cout<<endl;
system("PAUSE");
return 0;
}
/*
Given n (of size m) Linked lists
Print all set(head of linked list) of link list that intersect with each other.
e.g.
1-->2-->3-->4-->5
6-->7-->8-->4-->5
8->9->10->11->12
13->14->15->12
16->17->18
1 6
8 13
16
*/
#include<iostream>
#include<stack>
using namespace std;
class list
{
public:
int data;
list* next;
list(int data)
{
this->data = data;
next = NULL;
}
};
void displayAll(class list* heads[], int num)
{
class list* temp;
for(int i=0;i<num;i++)
{
temp = heads[i];
while(temp)
{
cout<<" "<<temp->data;
temp = temp->next;
}
cout<<endl;
}
}
void getHeadThatIntersect(class list* heads[], int num)
{
stack<list*> st[num];
for(int i=0;i<num;i++)
{
while(heads[i])
{
//cout<<" spot #"<<endl;
st[i].push(heads[i]);
heads[i] = heads[i]->next;
}
}
//cout<<" spot 1"<<endl;
for(int i=0;i<num;i++)
{
if(st[i].empty())
{
// cout<<" spot 2"<<endl;
continue;
}
else
{
list* temp = st[i].top();
// cout<<" spot 3 "<<temp->data<<endl;
for(int j = i+1;j<num;j++)
{
if(st[j].empty())
continue;
if(st[i].top() == st[j].top())
{
while(st[j].size() != 1)
st[j].pop();
cout<<" "<<((st[j].top())->data)<<" ";
st[j].pop();
}
if(j == num-1)
{
while(st[i].size() != 1)
st[i].pop();
cout<<" "<<((st[i].top())->data)<<" ";
st[i].pop();
}
}
cout<<endl;
}
}
}
int main()
{
// int num;
// cout<<" Enter the number of list :- ";
// cin>>num;
/************************************************/
//First List
list* head1 = new list(1);
head1->next = new list(2);
head1->next->next = new list(3);
head1->next->next->next = new list(4);
head1->next->next->next->next = new list(5);
//Second List
list* head2 = new list(6);
head2->next = new list(7);
head2->next->next = new list(8);
head2->next->next->next = head1->next->next->next;
//Third List
list* head3 = new list(8);
head3->next = new list(9);
head3->next->next = new list(10);
head3->next->next->next = new list(11);
head3->next->next->next->next = new list(12);
//Fourth List
list* head4 = new list(13);
head4->next = new list(14);
head4->next->next = new list(15);
head4->next->next->next = head3->next->next->next->next;
//Fifth List
list* head5 = new list(16);
head5->next = new list(17);
head5->next->next = new list(18);
/************************************************/
class list* heads[5] = {head1, head2, head3, head4, head5};
displayAll(heads, 5);
cout<<endl<<endl;
getHeadThatIntersect(heads, 5);
system("PAUSE");
return 0;
}
Repkylieblindner, abc at ASAPInfosystemsPvtLtd
Hello, I am Kylie. I am working in a store as Supply chain managers promote the design, development, and implementation ...
Repadak4257, Applications Developer at Adobe
I am fond of Listening Songs then reading newspapers which are all about a story of a beautiful nature and ...
Explanation :- if b>a then a-b will be negative, hence leftmost digit will be 1, if so, b is bigger else a.
- skum September 28, 2016