Microsoft Interview Question
Good answer, but there are cases where this wouldn't work.
For instance: Take the arrays [0,3] and [1,2].
0(d): 00(b)
1(d): 01(b)
2(d): 10(b)
3(d): 11(b)
Now 0^3 = 3 and 1^2 = 3. (^ is bitwise xor)
So they xor to the same answer, but aren't the same arrays.
Or did you mean something else with your answer?
I agree with Anonymous. Start off with zero; xor with all the elements in array 1; xor with all the elements in array 2. If you end up with zero, you have both array having same set of integers; otherwise not. Total O(n).
Can we just add them and compare the sum of both array, as if both of them has same set of integer than sum should be same......
PS: Don't worry about overflow that can be handled in a program.......
Sum of the squares of the two arrays should be the same if the both the arrays have the same set of numbers .
What is this? XOR, sum, sum of squares are all incorrect approaches. You could say that arrays are the same, when they actually are not.
Sorry to say this, but it seems like you guys need a course in basic math/logic.
sort each array using some fast algorithm like merge sort O(nlogn) and subtract corresponding element and put result in one of the two arrays. then scan that result array to find any non zero element. if found, it means they are not same.
use hashing....put numbers of array1 in hash....and go through numbers of array2 and check if it is in the hash....decrement count in hash if it's more than one element.. shud be O(n)
on a side note..this is set equality problem..and lower bound of set equality is O(nlogn) using any comparison based algorithm
Take product of all nos in both arrays See if products match
Take sum of all nos in both arrays See if sums match
If both match then the arrays may contain same ints
Add the elements of the first array in a binary tree. Now for every element in array 2, we try to insert in binary tree. In our binary tree we check the condition if the value already exists we, simply delete the node from the binary tree.
Thus, if the 2 arrays have the same elements then, at the end of the process the binary tree would be empty
We take the sum of the differences of each corresponding element, this must be zero for equality of the arrays.
ie a[0]-b[0]+a[1]-b[1]+...+a[n]-b[n] = 0
We take the sum of each array. This must also be same for equality.
ie a[0]+a[1]+...+a[n]=b[0]+b[1]+...+b[n]
Please cross-check. I haven't worked out its correctness.
I have one approach which runs in o(n) without extra space but valid only when you know the upper limit of number.
Suppose you are given that the number lies within 1-n where n is the size of array then you can easily find in o(n) by iterating a loop ar[abs(ar[i])%n]+=n;
Ex: ar1[]={2,3,1,4} then ar1 after loop becomes { 6,7,5,8}
ar2[] ={1,4,2,3} then ar2 becomes { 5,6,7,8} so in one loop you can easily count the number of times each index comes by diving by n and then checking elements in both arrays.
xor both the contents of the array
- Anonymous October 24, 2009