Find the number occuring odd number of times in an array

Given an array of positive integers. All numbers occur even number of times except one number which occurs odd number of times

We have to find the number which is occuring odd number of times in an array.

INPUT: 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6

OUTPUT: 4

Method 1

TIME COMPLEXITY – O(N)

SPACE COMPLEXITY – O(1)

We use the concept of XOR operation.

As we know,

A xor A = 0    ------------- Property 1

i.e. xor of two similar elements is zero.

Also,

A xor 0 = A  ---------------Property 2

i.e. xor of any element with zero gives the same number.

So our algorithm will be,

Algorithm

  1. Start from first element and loop through till last element of an array. Perform XOR of all elements on an array.
  2. XOR from point #1 will be Zero if the number occurs EVEN number of times [by property 1]
  3. XOR from point#1 will be equal to number if it is occurring odd number of times [by property 2]

Program for Method 1

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int arr[]= {1,1,2,2,3,3,4,4,4,5,5,6,6,7,7,8,8,9,9};
	int size = sizeof(arr)/sizeof(arr[0]);
	
	//initialize the value as first element
	int val = arr[0];
	for(int i=1;i<size;i++)
	{
		//XOR of each element so that we can find the number occuring odd number of times
		val = val^arr[i];
	}
	
	cout<<val<<" occurs odd number of times\n";
	return 0;
}
Try It


Method 2

TIME COMPLEXITY: O(N)

SPACE COMPLEXITY: O(N)

Add the elements of an array in an Hash or Map.

Algorithm

  1. Add the values in Hash or Map
  2. Make array element as key and the count of elements occurence as value of the key.
  3. Alfter adding all elements of an array, scan the map's value and wherever we get a number with odd count, then that key is the answer.

 

Program for Method 2

#include <bits/stdc++.h>
using namespace std;

//map to store 2 int values where first one is for the array element and second one for its count
map<int,int> M;
map<int,int>::iterator it;

int main()
{
	int arr[]= {1,1,2,2,3,3,4,4,4,5,5,6,6,7,7,8,8,9,9};
	int size = sizeof(arr)/sizeof(arr[0]);
	
	for(int i=0;i<size;i++)
	{
		it = M.find(arr[i]);
		
		// if the number is not present in the map then add it by making its count as 1
		if(it == M.end())
		{
			M.insert(make_pair(arr[i],1));
		}
		else	//if the number is present then simply increase its count by 1
		{
			pair<int,int> p = *it;
			M.erase(it);
			
			//p.second+1 is done for increasing the count by 1
			M.insert(make_pair(p.first,p.second+1));
		}
	}
	
	for(it = M.begin(); it != M.end(); it++)
	{
		//check for odd as if remainder is 1 then if evaluates to true
		if((it->second) % 2 )
		{
			cout << it->first << " occurs odd number of times\n";
			return 0;
		}
	}	

	return 0;
}
Try It

 

Method 3

TIME COMPLEXITY: O(N2)

SPACE COMPLEXITY: O(1)

Last and the most easily thinkable solution is to BRUTE FORCE the entire array.

Algorithm

  1. Take an element from array
  2. Run a loop from the start of array till end and keep on increasing the count whenever we encounter the taken element in point #1.
  3. If the count in point#2 is odd then we get the answer or else continue the scan for next elements of an array.

Program for Method 3

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int arr[]= {1,1,2,2,3,3,4,4,4,5,5,6,6,7,7,8,8,9,9};
	int size = sizeof(arr)/sizeof(arr[0]);
	
	//select each element as reference
	for(int i=0;i<size;i++)
	{
		int count_of_element = 0;
		for(int j=0;j<size;j++)
		{
			//if the number is same as the reference number
			if(arr[j] == arr[i])
				count_of_element++;
		}
		
		//check for odd as if remainder is 1 then if evaluates to true
		if(count_of_element % 2)
		{
			cout << arr[i] << " occurs odd number of times\n";
			return 0;
		}
	}
	
	return 0;
}
Try It

 


Next > < Prev
Scroll to Top