Amazon Interview Question Software Engineer / Developers
excellent solution @Cuppanomics
it is in fact O(n), the array need not be sorted for this.. try writing a function.
int func(int *A, int n)
{
int ret = 0;
for(int i=0;i<n;i++)
{
ret = ret^A[i];
}
return ret;
}
it is irrelevant if the number occurs once or any odd number of times (3, 5, 7, ..). The important thing is that there is only one such number that occurs an odd number of times. When XOR'ing the numbers, all even number will have a pair which will cancel it out. It doesn't matter how many times that even number occurs as the important thing is that all of them can be paired and thus canceled out.
For odd numbers the same thing applies. There will always be one lone element that cannot be paired with anything else. If it occurs 1 time, that is our element. If it occurs 3 or more times, then there will be 2n pairs that cancel out, and the 1 remaining element will be in our answer.
Read up more about XOR and commutativity and associativity at Wikipedia if you still have doubts.
Consider the following two input arrays:
1) {1,2,3,1,2,3,0,}
2) {1,2,3,1,2,3)
The XOR-ing algorithm will return 0 for both these inputs, but the correct output should be:
1) 0 occurs odd number of times.
2) No number found with odd number of occurences
Use a HAsh Table:
Algo:
1. While(i < arr.length)
{
if(HashTable.Contains(arr[i])
HashTable.Remove(arr[i]);
else
HashTable.Add(arr[i]);
i++;
}
if(HashTabl.isEmpty != TRUE)
{
return HashTable[arr[0]];
}
else
{ "NO ELEMENT WITH ODD OCCURENCE";
}
public int FindOddTimesOccurrence(int[] ar)
{
HashSet<int> values = new HashSet<int>();
foreach (int num in ar)
if (values.Contains(num))
values.Remove(num);
else
values.Add(num);
return values.First();
}
An exception will be thrown if there is number that occurs odd number of times. This solution requires an extra data structure- a set and runs in o(n). If there are ideas to this I would be glad to learn.
ok, I think there's another way of solving half of the problem:
sum up all the elements and if the sum is odd, we have an odd number odd number of times.
Divide the array in half and check the sum of one half and fetch the half whose sum is odd again. Keep doing this unless you get your number.
O(N) time and O(1) space.
But if your number is even, then we have to think of something else....
a XOR a = 0
- Cuppanomics May 11, 2010a XOR 0 = a
XOR all elements in array, the only number that occurs odd no. of times, will be the resultant