devendar
BAN USERstruct node * search(struct node *root, struct node *elem)
{
if(!root || !elem) return;
if(elem->right != NULL) {
elem = elem->right;
while(elem->left) {
elem = elem->left;
}
return elem;
}
struct node *result = NULL;
while(root) {
if(elem->data < root->data) {
result = root;
root = root->left;
}
else if (elem->data > root->data)
root = root->right;
else
break;
}
return result;
}
@rkt, is there a method to solve for the second case?
we can solve using xor.
1. xor of all the elements array and natural number 1 to n+1
Lets say we will get value 1(bit notation 0001)
2. divide the whole elements(array and natural numbers 1 to n+1) into two groups based on 1st bit(since resulting number in step1 has 1st bit 1).
one group of numbers which has all the 1st bits is 1
second group of numbers which has all the 1st bits is 0.
3. apply xor on first group you will get one number
4. apply xor on second group you will get second number.
TC. - O(n+n+n) = O(n)
SC - O(1)
-Devendar
1. sort B - nlogn
- devendar September 19, 20122. take one element from A, search for the second element in B(using binary search) - nlogn
total - nlogn