Given an array arr[] of N elements, the task is to find the XOR of the elements which appear an odd number of times in the array.
Examples:
Input: arr[] = {1, 2, 1, 3, 3, 4, 2, 3, 1}
Output: 6
Elements with odd frequencies are 1, 3 and 4.
And (1 ^ 3 ^ 4) = 6Input: arr[] = {2, 2, 7, 8, 7}
Output: 8
Naive Approach: Traverse the array and store the frequencies of all the elements in a unordered_map. Now, calculate the XOR of elements having odd frequency using the map created in the previous step.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the xor of// elements having odd frequencyint xorOdd(int arr[], int n){ // To store the frequency // of all the elements unordered_map<int, int> m; // Update the map with the // frequency of the elements for (int i = 0; i < n; i++) m[arr[i]]++; // To store the XOR of the elements // appearing odd number of // times in the array int xorArr = 0; // Traverse the map using an iterator for (auto it = m.begin(); it != m.end(); it++) { // Check for odd frequency // and update the xor if ((it->second) & 1) { xorArr ^= it->first; } } return xorArr;}// Driver codeint main(){ int arr[] = { 1, 2, 1, 3, 3, 4, 2, 3, 1 }; int n = sizeof(arr) / sizeof(arr[0]); cout << xorOdd(arr, n); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{ // Function to return the xor of// elements having odd frequencystatic int xorOdd(int arr[], int n){ // To store the frequency // of all the elements HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); // Update the map with the // frequency of the elements for (int i = 0 ; i < n; i++) { if(mp.containsKey(arr[i])) { mp.put(arr[i], mp.get(arr[i]) + 1); } else { mp.put(arr[i], 1); } } // To store the XOR of the elements // appearing odd number of // times in the array int xorArr = 0; // Traverse the map using an iterator for (Map.Entry<Integer, Integer> it : mp.entrySet()) { // Check for odd frequency // and update the xor if (((it.getValue()) % 2) ==1) { xorArr ^= it.getKey(); } } return xorArr;}// Driver codepublic static void main(String[] args){ int arr[] = { 1, 2, 1, 3, 3, 4, 2, 3, 1 }; int n = arr.length; System.out.println(xorOdd(arr, n));}}// This code contributed by PrinciRaj1992 |
Python3
# Python3 implementation of the approach# Function to return the xor of # elements having odd frequency def xorOdd(arr, n) : # To store the frequency # of all the elements m = dict.fromkeys(arr, 0); # Update the map with the # frequency of the elements for i in range(n) : m[arr[i]] += 1; # To store the XOR of the elements # appearing odd number of # times in the array xorArr = 0; # Traverse the map using an iterator for key,value in m.items() : # Check for odd frequency # and update the xor if (value & 1) : xorArr ^= key; return xorArr; # Driver code if __name__ == "__main__" : arr = [ 1, 2, 1, 3, 3, 4, 2, 3, 1 ]; n = len(arr); print(xorOdd(arr, n)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System;using System.Collections.Generic; class GFG{ // Function to return the xor of// elements having odd frequencystatic int xorOdd(int []arr, int n){ // To store the frequency // of all the elements Dictionary<int, int> mp = new Dictionary<int, int>(); // Update the map with the // frequency of the elements for (int i = 0 ; i < n; i++) { if(mp.ContainsKey(arr[i])) { mp[arr[i]] = mp[arr[i]] + 1; } else { mp.Add(arr[i], 1); } } // To store the XOR of the elements // appearing odd number of // times in the array int xorArr = 0; // Traverse the map using an iterator foreach(KeyValuePair<int, int> it in mp) { // Check for odd frequency // and update the xor if (((it.Value) % 2) == 1) { xorArr ^= it.Key; } } return xorArr;}// Driver codepublic static void Main(String[] args){ int []arr = { 1, 2, 1, 3, 3, 4, 2, 3, 1 }; int n = arr.Length; Console.WriteLine(xorOdd(arr, n)); }}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript implementation of the approach// Function to return the xor of// elements having odd frequencyfunction xorOdd(arr, n){ // To store the frequency // of all the elements let mp = new Map(); // Update the map with the // frequency of the elements for(let i = 0 ; i < n; i++) { if (mp.has(arr[i])) { mp.set(arr[i], mp.get(arr[i]) + 1); } else { mp.set(arr[i], 1); } } // To store the XOR of the elements // appearing odd number of // times in the array let xorArr = 0; // Traverse the map using an iterator for(let [key, value] of mp.entries()) { // Check for odd frequency // and update the xor if (((value) % 2) == 1) { xorArr ^= key; } } return xorArr;}// Driver codelet arr = [ 1, 2, 1, 3, 3, 4, 2, 3, 1 ];let n = arr.length;document.write(xorOdd(arr, n));// This code is contributed by rag2127</script> |
Output:
6
This solution takes O(n) time and O(n) space.
Efficient Approach:
This approach uses two important properties of XOR – a ^ a = 0 and 0 ^ a = a. Take XOR of all the elements in the array. The result will be the XOR of numbers that appears an odd number of times since elements appearing even number of times eventually cancel out each other.
C++
// C++ program to implement// the above approach#include<bits/stdc++.h>using namespace std;int xorOdd(int arr[], int n) { // initialise result as 0 int result = 0; // take XOR of all elements for (int i = 0; i < n; ++i) { result ^= arr[i]; } // return result return result;}// Driver codeint main() { int arr[] = { 1, 2, 1, 3, 3, 4, 2, 3, 1 }; int n = sizeof(arr) / sizeof(arr[0]); cout << xorOdd(arr, n); return 0; } |
Java
// Java program to implement// the above approachimport java.io.*;class GFG{static int xorOdd(int arr[], int n) { // Initialise result as 0 int result = 0; // Take XOR of all elements for(int i = 0; i < n; ++i) { result ^= arr[i]; } // Return result return result;}// Driver codepublic static void main (String[] args) { int arr[] = { 1, 2, 1, 3, 3, 4, 2, 3, 1 }; int n = arr.length; System.out.println(xorOdd(arr, n));}}// This code is contributed by math_lover |
Python3
# Python3 program to implement# the above approachdef xorOdd(arr, n): # Initialise result as 0 result = 0 # Take XOR of all elements for i in range (n): result ^= arr[i] # Return result return result# Driver codeif __name__ == "__main__": arr = [1, 2, 1, 3, 3, 4, 2, 3, 1] n = len(arr) print( xorOdd(arr, n)) # This code is contributed by Chitranayal |
C#
// C# program to implement// the above approachusing System;class GFG { static int xorOdd(int[] arr, int n) { // Initialise result as 0 int result = 0; // Take XOR of all elements for (int i = 0; i < n; ++i) { result ^= arr[i]; } // Return result return result; } // Driver code public static void Main() { int[] arr = { 1, 2, 1, 3, 3, 4, 2, 3, 1 }; int n = arr.Length; Console.Write(xorOdd(arr, n)); }}// This code is contributed by rishavmahato348. |
Javascript
<script>// Javascript program to implement// the above approachfunction xorOdd(arr, n) { // initialise result as 0 let result = 0; // take XOR of all elements for (let i = 0; i < n; ++i) { result ^= arr[i]; } // return result return result;}// Driver code let arr = [ 1, 2, 1, 3, 3, 4, 2, 3, 1 ]; let n = arr.length; document.write(xorOdd(arr, n)); </script> |
Output:
6
This solution takes O(n) time and O(1) space.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
