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[0]; //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)

## 3 comments

I get ur point :)

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

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.

Comments are closed.