Find the number occurring odd number of times in an array

You are given an array of integers. All the numbers in array occurs even number of times except the one which occurs odd number of time. You have to find the number in O(N) time and constant space.

For eg. 1,4,6,7,3,1,4,7,3,1,6 (given array)
Output: 1

Solution: Take bitwise XOR of all the elements. We will get the number with odd occurrence.

#include <stdio.h>
// function that will check for odd occurring number
int findOddOccurringNumber(int *a, int n)
     int op = 0; 
     for (int i=0; i < n; i++)     
        op = op ^ a[i];
     return op;

int main()
     int a[] = {1,4,6,7,3,1,4,7,3,1,6};
     int n = sizeof(a)/sizeof(a[0]);
     cout << findOddOccurringNumber(a,11);
     return 0;

Time complexity: O(N), Space Complexity: O(1)

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation