Find the number which occurs odd number of times

In an integer array, except for one number which occurs odd number of times, all other numbers occur even number of times. Find the number.

Example:
Input: 2 3 4 3 1 4 5 1 4 2 5
Output: 4

Algorithm:
Initialize result = 0.
Iterate over the array and XOR result with each element of the input array.
Once iteration over the array is done, print result as the output.

Order of the Algorithm:
Time Complexity: O(n)
Space Complexity: O(1)

Code and Algorithm Visualization:

[IDeserve]

Dear Friends,

If you like our content and would like us to continue making great content for you, please spread the word about IDeserve.
A share/appreciation from you on social network would mean the world to us!


Thanks,
-Team IDeserve.

[varun-bhandari]

Code Does not work for this input : {2, 7, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2, 7, 4, 4};
Returns '6' which is not even in the array.

[ashishgupta]

but for serching pairs it will take more than o(n)

[umangbarbhaya]

//java code

class Test {
public static void main(String args[]) {

// x is stored using 32 bit 2's complement form.
// Binary representation of -1 is all 1s (111..1)
int a[] = {2, 3, 4, 3, 1, 4, 5, 1, 2, 4, 5};
int ans=a[0];
for(int i=1;i<a.length;i++)
{
ans=ans^a[i];
}
System.out.println(ans);


}
}