Home Arrays Find the number occuring odd number of times in an array.

# Find the number occuring odd number of times in an array.

Question: 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 and constant space.

Input:- arr[] = {1, 2, 3, 2, 3, 1, 3}
Output:- 3

This is a very simple problem. The basic and naive approach will be to scan the complete array and keep a track of each element. We need to count the occurrence of each element and see if its even or odd. This would be a very hectic problem. We can utilize the property of bit-wise XOR operator to make an easy solution.

A XOR A = 0 (zero)

So we can make a solution as:-

#include<stdio.h>

int main(void)
{
//an array of 7 elements
int arr[] = {1, 2, 3, 2, 3, 1, 3};

int i = 0;
int x = arr;

//iterate through the array
for(i = 1; i<7 ; i++)
{
// do a bit-wise XOR of all the elements
x = x ^ arr[i];
}

// all the even elements are converted to 0, only the odd one remains
printf("The number occurring odd number of times is = %d", x);

return 0;
}


Time Complexity:- O(n)
Space Complexity:- O(1)

#### You may also like February 23, 2015 - 00:04

I get ur point :) February 12, 2015 - 01:16

what are all the constraints in this problem ?,I mean like, are -ve values allowed and why would we require to know if a number is odd or even February 21, 2015 - 01:16

Negative numbers are not allowed, however it would be a nice exercise to try this method with negative numbers and see the result.
I like the second part of your comment. Why would you need to find?
This problem will never be a straight forward question but will rather come up as a part of some bigger problem. There lies your smartness to apply the most efficient method.