Description: Given an array where each element occurs even number of times except one element, which occurs odd number of times. We have to find that number.

 
If video does not load, Click here
 
Example:

Input:

2  2  4  3  4  3  4ut:x=ppwqkrfoqkd[as

Output:

4

Algorithm:

  1. Intialize a variable ‘x’ as 0.
  2. Scan through the elements of the array using index ‘i’ taking bitwise xor with ‘x’.

                          x =x (xor) arr[i]

  3. ‘x’ stores the number occuring odd number of times.Implementation in C:

Implementation in C:

/*The following function returns number occuring odd number of times.*/

int oddoccurence(int arr[],int n)

{

     int k;

     int x = 0;

     for (k=0; k <n; k++)    

        x = x ^ arr[k];     

     return x;

/*'x' stores the number occuring odd number of times.*/

}Time Complexity :

Time Complexity:

O(n)

Go to top