Saurabh2816
BAN USER- 0 Answers Is my approach correct?
Problem : There is a hill and few taps are present, all connected to other taps above/below, find which tap will be the last one to get water from a spring on the top of the mountain.
- Saurabh2816 August 05, 2015
My Approach : Now I understand this is a connected graph problem. And by doing Breadth First Traversal we can get the last tap which will get the water.
Doubt : 1. Is my solution correct? If yes, then does BFT always gives the right answer? 2. Is there any other approach I'm not seeing?| Flag | PURGE
I had hard time understanding the solution(s) mentioned here. So if you guys are facing the same problem here is the link for better understanding. Upvote so everybody can see.
geeksforgeeks.org/find-the-two-numbers-with-odd-occurences-in-an-unsorted-array/
Theory
sum = a xor b xor c
carry = ab + bc+ ac
Code
int addBinary(int a1[], int a2[], int result[]){
int i, c = 0;
for(i = 0; i < 8 ; i++){
result[i] = ((a1[i] ^ a2[i]) ^ c); //a xor b xor c
c = ((a1[i] & a2[i]) | (a1[i] &c)) | (a2[i] & c); //ab+bc+ca
}
result[i] = c;
return c;
}
Using any of the traversal algorithms, keep track of max1 and max2 (max1 = maximum node in the tree).
When you encounter a new node, you compare it with max1 first, and if the node is bigger you move max1 to max2. Or if it's smaller, compare it with max2 also.
Here is my implementation.
- Saurabh2816 August 20, 2014