Finding the number, occurring odd number of times in an array
Given an array arr[] of n integers, find a number which occurred odd times in the array. If such an element exists, print that respective element, else print There is no odd occurring element.
Note: The array should contain at most one odd times occurring number.
Method 1 ( Hashing ):
Approach: Create an empty hash table. Copy the input array elements into the HashMap such that it contains key as element and value as frequency( count of occurrences ) of that element. Now traverse the HashMap and check for the odd occurrence using divisibility test. If found, print the element.
For example:
In the above example, the input elements {2, 3, 10, 5, 2, 10, 10, 5, 3} are mapped into a hash table with keys {2, 3, 5, 10} with respective values {2, 2, 2, 3}.
When HashMap is traversed from the beginning, the odd occurred element (here 10) can be found with a divisibility test(by 2).
Complexity Analysis : Time Complexity : O(n) Space Complexity: O(n)
{tab title="C++" class="green"}
/* The code is contributed by Tangudu Sai Kiran. */
//A C++ program to find the odd times occurring element from a given input array using Hashing
#include <bits/stdc++.h>
using namespace std;
//Function to find element which occurred odd number of times
void findOccurance(int n, int arr[])
{
//Defining a HashMap
unordered_map<int, int> elements;
//Inserting elements into the Hashmap
for(int i = 0; i < n; i++)
elements[arr[i]]++;
//Iterate through the hashmap to find odd occurring element if exists
for(auto it : elements)
{
//checking for majority condition
if(it.second % 2 != 0){
cout<<"ODD OCCURRING ELEMENT: "<< it.first<< endl;
return;
}
}
cout<<"THERE IS NO ODD OCCURRING ELEMENT"<<endl;
return;
}
int main()
{
int arr[] = {6, 5, 2, 5, 4, 2, 6};
int n = sizeof(arr) / sizeof(arr[0]);
//Function call
findOccurance(n, arr);
return 0;
}{tab title="Java" class="orange"}
/* The code is contributed by Tammisetti Naveen */
//A JAVA program to find odd times occurring number using Hashing
import java.util.HashMap;
public class OddOccurrenceElement
{
//function to find the element which occurs odd no of times
static void FindOccurence (int n, int arr[]) {
HashMap<Integer,Integer> Hsmap = new HashMap<Integer, Integer>();
for (int i = 0; i < n; i++)
{
//if the key is repeated, its value is incremented else element is added and its frequency is 1
if (Hsmap.containsKey(arr[i]))
{
Hsmap.put (arr[i], Hsmap.get(arr[i]) + 1);
}
else
{
Hsmap.put(arr[i], 1);
}
}
for (int i = 0;i < n; i++)
{
if(Hsmap.get(arr[i]) % 2 != 0)
{
System.out.print (arr[i]);
return;
}
}
System.out.println ("THERE IS NO NUMBER OCCURRING ODD NUMBER OF TIMES");
}
public static void main(String args[])
{
int arr[] = {6, 5, 2, 5, 4, 2, 6};
int n = arr.length;
//Function call
FindOccurence(n, arr);
}
}{tab title="Python" class="red"}
//Hashing method to find which occurrence odd number of times
def findOddOccurence(array):
d=dict()#to store key:value pairs
for i in array:
if i in d:
d[i]+=1 #if element is present then increment its value by 1
else:
d[i]=1 #if element not present then initialize its value to 1
for j in d.keys():
if d[j]%2!=0:
print('THE NUMBER OCCURRING ODD TIMES:', j)
return
print('THERE IS NO NUMBER OCCURRING ODD NUMBER OF TIMES')
if __name__=="__main__":
array=[6, 5, 2, 5, 4, 2, 6]
findOddOccurence(array)
{/tabs}
Method 2 ( Using XOR)
This is the most effective and efficient algorithm to find an odd occurring element from a given array. It uses two basic properties of XOR: Self-inverse and Identity properties which mean-Any element XORed with itself gives zero(A ⊕ A = 0) and any element XOR’d with zero left unchanged (A ⊕ 0 = A) respectively.
Approach: Initialize a variable( say result ) to 0. Traverse the array from the beginning and Compute XOR of each and every element with the result variable. So outputting the result variable gives the desired output.
For example
Complexity Analysis :
Time Complexity : O(n)
Space Complexity: O(1)
{tab title="C++" class="green"}
//A C++ program to find odd Occurrence of element in an given array using XOR method
//XOR METHOD
/* The code is contributed by Tangudu Sai Kiran. */
//A C++ program to find the odd times occurring element from a given input array using Hashing
#include <bits/stdc++.h>
using namespace std;
//Function to find element which occurred odd number of times
void findOccurance(int n, int arr[])
{
//Defining a HashMap
unordered_map<int, int> elements;
//Inserting elements into the Hashmap
for(int i = 0; i < n; i++)
elements[arr[i]]++;
//Iterate through the hashmap to find odd occurring element if exists
for(auto it : elements)
{
//checking for majority condition
if(it.second % 2 != 0)
{
cout<<"ODD OCCURRING ELEMENT: "<< it.first<< endl;
return;
}
}
cout<<"THERE IS NO ODD OCCURRING ELEMENT"<<endl;
return;
}
int main()
{
int arr[] = {6, 5, 2, 5, 4, 2, 6};
int n = sizeof(arr) / sizeof(arr[0]);
//Function call
findOccurance(n, arr);
return 0;
}
{tab title="Java" class="orange"}
//A JAVA program to find odd Occurrence of element in an given array using XOR method
//XOR METHOD
public class findOccurrenceNumber
{
static void findOccurrence(int n, int arr[])
{
int result = 0;
for (int i = 0; i < n; i++)
result = result ^ arr[i];
if(result == 0)
System.out.println("No odd times occurring element");
else
System.out.print("Odd times occurring element:"+result);
}
public static void main(String[] args)
{
int arr[] = {6, 5, 2, 5, 4, 2, 6};
int n = arr.length;
findOccurrence(n, arr);//Function call
}
}
{tab title="Python" class="red"}
//XOR method to find odd Occurrence of element in array
def findOddOccurence(array):
r=0
for i in array:
r=r^i
print(r)
if __name__=="__main__":
array=[6, 5, 2, 5, 4, 2, 6]
findOddOccurence(array)
{/tabs}