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

Start from first element and loop through till last element of an array. Perform XOR of all elements on an array.

XOR from point #1 will be Zero if the number occurs EVEN number of times [by property 1]

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;
}
Method 2
TIME COMPLEXITY: O(N)
SPACE COMPLEXITY: O(N)
Add the elements of an array in an Hash or Map.
Algorithm

Add the values in Hash or Map

Make array element as key and the count of elements occurence as value of the key.

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;
}
Method 3
TIME COMPLEXITY: O(N^{2})
SPACE COMPLEXITY: O(1)
Last and the most easily thinkable solution is to BRUTE FORCE the entire array.
Algorithm

Take an element from array

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.

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;
}