CareerCup

My answer I gave was to put all the numbers in a hash table where the key where the numbers and the values where the number of times the number was seen. Then just go through all the numbers and see which ones are not divisible by 2. This was the best answer I could come up with on the spot, and I wasn't able to answer the last part of how it could be done without another data structure.

XOR all of 'em

result = 0;
for each element
{
result ^= element[i];
}
return result;

sum all the numbers. subtract one element at a time, if result is even the number just subtracted is answer. the xor solution is best imo.

Are u sure for XOR answer ??


public class Xor {

public static void main(String[] args) {
int arr[] = { 1,1,1,2,2,3,4,4,4,7,7,5};
int result = 0;
for (int i = 0; i < arr.length; i++) {
result = result ^ arr[i];
//System.out.println( (i+1) + ": " + result);
}

System.out.println("Final Result : " + result);

}
}

The result that was given is 3 instead of 2 .

@Hi : Always read the question carefully.
XORing is the best answer for such even-odd occurrence questions.

Just FYI to any potential Amazon interviewees -- this question or a variation of it is VERY common, and I've seen it every time I was interviewed. Knowing the XOR answer will put you ahead of a lot of people.

Hi ,

I just thought of another way of doing it.

product all the numbers.
divide the product by each of the numbers. Find the square root of the division. If its whole. then the integer is odd one. as even number of integer multiplication should have whole square root.


but again no zeroes here. but seriously,, how the hell did u come up XOR man??!!

Q: An integer array where there are repeating numbers and all but one repeat an odd number of times ex [ 2,2,2,4,4,7,7,7,3,5] 4 repeats even number of times, [2,1,7,3,3] 3 repeats even number of times . Find it

A: Do an XOR of the corresponding bits of integers in the array, and do a NOT on the result

a good test case for this solution is, {0,1,1,2,2} ;-)

Please read the question carefully it is not that straight forwards "All but one is repeated even number of times" and we have to find any one which is repeated odd number of times. So, here the XOR wont work.