codemaniac
BAN USERThere is 1 case where this will not work. What if the 2 linked lists have same elements before the intersection point? In that case this algorithm will not give the correct intersection point. For eg -
1->2->3->3->3->4>5->6
10->11->3->3->3->20
Assume that the 2nd list points to the node with 5 in the 1st list
It will give the intersection point as 3, where as it is 7th number
- codemaniac February 26, 2012agreed :) the XOR based solution is better ...
- codemaniac February 10, 2012hmmm. True. This solution works only for smaller number of elements where their products do not overflow. Were you able to get a proper solution for this problem ?
- codemaniac February 09, 2012Add the numbers in both the arrays to get their sums : S1 , S2. Where
S1 = a[0] + a[1] + X + Y+ ..+a[n]+a[n+1] &
S2 = b[0] + b[1] .. + b[n-2] + b[n-1]
so X + Y = S1 - S2
Iterate through the arrays again and get the product of the elements in each array : P1 , P2
P1 = a[0] * a[1] * X * Y * ..a[n]*a[n+1]
P2 = b[0] * b[1] * .. b[n-2] * b[n-1]
So X*Y = P1/P2
We now have 2 equations :
X +Y = S1 - S2 &
X*Y = P1/P2
We can solve these to get the missing numbers in array b - X & Y. This will require 2 iterations of both the arrays. So the time complexity is O(n) and space is O(1).
The only downside of this technique is that if any of the array element is 0, this will not work.
Here is an iterative version of the code to find the duplicate element. It works in O(log n) time -
int nums[] = { 1,2,3,4,5,6,7,7,8};
int low = 0, high = 9;
while(low<high){
if( nums[ (low + high)/2 ] <= (low+high)/2 )
high = (low + high)/2 -1 ;
else
low = (low + high) /2 + 1;
}
printf("The duplicate number is : %d ", nums[low] );
This will be a O(n) solution
- codemaniac February 09, 2012I don't think this will work. Assume that the input is 7 (0111) . During the 1st call to this function the condition in the if statement will turn out to be true -
(0111 & 0001) = 0001 = true
so count will be returned as 1, but it is actually 3.
Let me know in case i am wrong.
it will not work for this case -
- codemaniac February 29, 20120-0-0-0
1-0-0-0
1-0-0-0
1-1-1-1