find no occured odd no of times

hey this question from geeksfor geeks ::::: Given an array of positive integers. All numbers occur even number of times except one number which occurs odd number of times. Find the number in O(n) time & constant space.

Example:
I/P = [1, 2, 3, 2, 3, 1, 3]
O/P = 3

can anybody give some approach??

1 Like

just a hint…try using some bitwise operator…hope this helps…:slight_smile:

3 Likes

As @kunal361 mentioned, the trick is to use bitwise operators. If you analyse the problem carefully, you will notice that as the number of terms for all the numbers are even except for one, they cancel out. This means that, for every one number, there exists some other number (of the same type obviously). If we do this for each and every number, we would find that one number exists such that it does not have a term to cancel out with… in this case it is 3. All other numbers have a cancelling counter-pair. So now to solve this problem, one probable solution would be to alternatively add and subtract pairs of numbers, till we find one number which does not result in 0 as the answer. This would not satisfy the space and time complexities that are specified. So another technique would be to use the XOR operation. XOR operation nullifies same bits. 0 ^ 0 =0 and 1^1 = 0.Also XOR is associative and commutative(Can take any order of numbers and still get the same result). So performing XOR operation on all the numbers would result in a nonzero answer at the end. This answer is the term which occurs odd number of times.

1 Like

nice explanation…but u took the fun out of the problem for him…he just asked for an approach…:stuck_out_tongue:

1 Like