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

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

by nikoo28
3 comments

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

You may also like

3 comments

Shantun Rubal February 23, 2015 - 00:04

I get ur point :)

Reply
Shantun Rubal 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

Reply
nikoo28 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.

Reply

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More