Problem Statement: Given an array of positive integers, where all elements are occurring even a number of times except one which is occurring an odd number of times.
Examples:
Example 1:
Input: arr = {1,2,3,2,3}
Output: 1
Explanation: only one element is occuring odd number of times i.e. 1 .
Example 2:
Input: arr = {4,5,6,5,6,9,9,4,4}
Output: 4
Explanation: Only one element is occuring odd number of times i.e. 4 .
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution 1:
Approach:
The approach is very simple where we will run two nested loops, and count the occurrence of every element. If at any moment, we are getting the count as odd, we will just print that element.
For eg , - arr = {1 , 2 , 3 , 2 , 1}
- The first iteration – 1 is occurring 2 times
- The second iteration – 2 is occurring 2 times
- The third iteration – 3 occurs 1 time (odd number of times).
This means the answer is ‘3’.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
// Function to find one odd occuring element
int findoddoccuring(int arr[], int n)
{
for (int i = 0; i < n; i++)
{
int count = 0;
for (int j = 0; j < n; j++)
{
if (arr[i] == arr[j])
count++;
}
if (count%2!=0)
return arr[i];
}
return -1;
}
int main()
{
int n = 5;
int arr[] = {1, 2, 3, 2, 1};
cout << findoddoccuring(arr, n)<<" is occurring an odd number of times"<< endl;
return 0;
}
Output: 3 is occurring an odd number of times
Time Complexity: O( n2 ), since we are using nested loop
Space Complexity: O(1)
Java Code
import java.util.*;
public class Main {
// Function to find one odd occuring element
public static int findoddoccuring(int[] arr, int n) {
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = 0; j < n; j++) {
if (arr[i] == arr[j])
count++;
}
if (count%2!=0)
return arr[i];
}
return -1;
}
public static void main(String args[]) {
int n = 5;
int[] arr = {1, 2, 3, 2, 1};
System.out.println(findoddoccuring(arr, n)+" is occurring an odd number of
times");
}
}
Output: 3 is occurring an odd number of times
Time Complexity: O( n2 ), since we are using nested loop
Space Complexity: O(1)
Solution 2:
Approach:
Approach 2 is also simple where we will use hash data structure So here we will be using extra auxiliary space of O(n). Here we will count occurrences of every element.
(Note that – hash stores distinct elements and it stores key, value pair )
For eg , - arr = {1 , 2 , 3 , 2 , 1}
Creating a hash map
Element occurrences 1 | 2 2 | 2 3 | 1
Since occurrences of ‘3’ are 1 . So it is the odd occurring element.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
// Function to find one odd occuring element using hashing
int findoddoccuring(int arr[], int n)
{
map<int, int> mp;
for (int i = 0; i < n; i++)
{
mp[arr[i]]++;
}
for (auto it : mp)
{
if (it.second % 2 != 0)
return it.first;
}
return -1;
}
int main()
{
int n = 5;
int arr[] = {1, 2, 3, 2, 1};
cout<<findoddoccuring(arr, n)<<" is occurring an odd number of times"<<endl;
return 0;
}
Output: 3 is occurring an odd number of times
Time Complexity: O(n), where n is the size of the array
Space Complexity: O(n), auxiliary space required for hash data structure
Java Code
import java.util.*;
public class Main {
// Function to find one odd occuring element using hashing
public static int findoddoccuring(int[] arr, int n) {
HashMap < Integer, Integer > mp = new HashMap < > ();
for (int i = 0; i < n; i++) {
if (mp.containsKey(arr[i]))
// mp.get(arr[i]) - gives us previous count
// increment it by 1
// and put in the map again
mp.put(arr[i], mp.get(arr[i]) + 1);
else
mp.put(arr[i], 1);
}
for (Integer it: mp.keySet()) {
if (mp.get(it) % 2 != 0)
return it;
}
return -1;
}
public static void main(String args[]) {
int n = 5;
int[] arr = {1, 2, 3, 2, 1};
System.out.println(findoddoccuring(arr, n)+" is occurring an odd number of
times");
}
}
Output: 3 is occurring an odd number of times
Time Complexity: O(n), where n is the size of the array
Space Complexity: O(n), auxiliary space required for hash data structure
Solution 3 :
Approach:
The Best approach is bitwise Xor all elements of the array where even occurring elements on xor will give 0 whereas odd occurring element on xor give us the number since its even occurrence will give 0.
For Eg - arr = {7,2,3,3,2,7,7}
^ represents xor
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
// Function to find one odd occuring element using xor
int findoddoccuring(int arr[], int n)
{
int xorele = 0;
for (int i = 0; i < n; i++)
xorele = xorele ^ arr[i];
return xorele;
}
int main()
{
int n = 5;
int arr[] = {1, 2, 3, 2, 1};
cout<<findoddoccuring(arr, n)<<" is occurring an odd number of times"<<endl;
return 0;
}
Output: 3 is occurring an odd number of times
Time Complexity: O(n) for taking the xor of n elements
Space Complexity: O(1)
Java Code
import java.util.*;
public class Main {
// Function to find one odd occuring element using xor
public static int findoddoccuring(int[] arr, int n) {
int xorele = 0;
for (int i = 0; i < n; i++)
xorele = xorele ^ arr[i];
return xorele;
}
public static void main(String args[]) {
int n = 5;
int[] arr = {1, 2, 3, 2, 1};
System.out.println(findoddoccuring(arr, n)+" is occurring an odd number of
times");
}
}
Output: 3 is occurring an odd number of times
Time Complexity: O(n) for taking the xor of n elements
Space Complexity: O(1)
Special thanks to Gurmeet Singh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article