Sai
BAN USERMy thoughts:
1) As any number can be swapped only with '0' -> The relative position of most of the numbers should be same, except the case of 1st position.
2) Zero always bubbles up to the first position, its like every new car gets to park on the top of the stack, so which means either (here zero travelling is nothing but swapping)
- Zero travels all the way to right-most and get swapped with left-most element.
- Zero travels all the way to the left-most
So if we consider target possibility of given src={1,0,2,3} would be either
Case 1: tgt={0,2,3,1} - Which is zero travels right-most and gets swapped with left-most element.
or
Case 2: tgt={0,1,2,3} - Which is zero travels left-most
I mean we compare src[0] with tgt[0] and decide whether to take zero to travel in which direction.
I might be assuming lot of things like
If we assume tgt[0] is always zero then tgt possibilities would be (n-1)!, so by assuming relative position I am ruling out all tgt possibilities except two.
So for {X, , , } => 1, 2, 3 can be arranged in 3! = 6 ways, but I am ruling out {0, 2, 1, 3}, {0, 3, 1, 2}, {0, 3, 2, 1} and {0, 1, 3, 2}
Sai
I think the solution might be correct as we have to look at subarray in C whose sum is zero not just C....so if we see C={-11-11} the sum is zero for i=0,j=3
So its basically we are finding i & j where we have equal no of 0`s or 1`s:
Case 1: i=0, j = 0
Sum[A(i,j)] = 0, Sum[B(i,j)] = 1, j-i=0 -> (invalid case as sum A(i,j) not equal to sum B(i,j))
Case 2: i=0, j = 1
Sum[A(i,j)] = 1, Sum[B(i,j)] = 1, j-i=1
Case 3: i=0, j = 2
Sum[A(i,j)] = 1, Sum[B(i,j)] = 2, j-i=2 -> (invalid case as sum A(i,j) not equal to sum B(i,j))
Case 4: i=0, j = 3
Sum[A(i,j)] = 2, Sum[B(i,j)] = 2, j-i=3
Among the valid cases if you see i=0, j=3 is the indices which satisfies both the given conditions and you you have the same from finding the longest sub array from C[i]=A[i]-B[i]
Lets consider another example:
[i] 0 1 2 3 4 5 6 7 8 9 10
A=[ 0 1 0 0 0 1 0 0 1 0 0]
B=[ 1 0 1 1 1 0 1 1 0 1 0]
C=[-1 1 -1 -1 -1 1 -1 -1 1 -1 0]
So the longest sub-array in C whose sum is zero => i = 5 & j = 8
Sum[A(5,8)] = 2, j-i = 3
Sum[B(5,8)] = 2, j-i = 3
One more:
A=[001000100]
B=[000001000] -> i=3, j= 8
Thanks Anonymous for this solution, let me see if I come up with any negative test case to fail you algorithm.
Can we use some thing like network mask 255.255.255.0 or 255.255.0.0 as a hash function......it really depends whether you need 255 buckets or 255 * 255 buckets
- Sai October 31, 2013