Given an array of positive integers. All numbers occur an even number of times except one number which occurs an odd number of times. Find the number in O(n) time & constant space.
Examples :
Input : arr = {1, 2, 3, 2, 3, 1, 3}
Output : 3Input : arr = {5, 7, 2, 7, 5, 2, 5}
Output : 5
A Simple Solution is to run two nested loops. The outer loop picks all elements one by one and the inner loop counts the number of occurrences of the element picked by the outer loop. The time complexity of this solution is O(n2).
Below is the implementation of the brute force approach :
C++
// C++ program to find the element // occurring odd number of times#include<bits/stdc++.h>using namespace std; // Function to find the element // occurring odd number of timesint getOddOccurrence(int arr[], int arr_size){ for (int i = 0; i < arr_size; i++) { int count = 0; for (int j = 0; j < arr_size; j++) { if (arr[i] == arr[j]) count++; } if (count % 2 != 0) return arr[i]; } return -1;} // driver codeint main() { int arr[] = { 2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2 }; int n = sizeof(arr) / sizeof(arr[0]); // Function calling cout << getOddOccurrence(arr, n); return 0; } |
Java
// Java program to find the element occurring// odd number of timesclass OddOccurrence { // function to find the element occurring odd // number of times static int getOddOccurrence(int arr[], int arr_size) { int i; for (i = 0; i < arr_size; i++) { int count = 0; for (int j = 0; j < arr_size; j++) { if (arr[i] == arr[j]) count++; } if (count % 2 != 0) return arr[i]; } return -1; } // driver code public static void main(String[] args) { int arr[] = new int[]{ 2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2 }; int n = arr.length; System.out.println(getOddOccurrence(arr, n)); }}// This code has been contributed by Kamal Rawal |
Python3
# Python program to find the element occurring# odd number of times # function to find the element occurring odd# number of timesdef getOddOccurrence(arr, arr_size): for i in range(0,arr_size): count = 0 for j in range(0, arr_size): if arr[i] == arr[j]: count+=1 if (count % 2 != 0): return arr[i] return -1 # driver code arr = [2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2 ]n = len(arr)print(getOddOccurrence(arr, n)) # This code has been contributed by # Smitha Dinesh Semwal |
C#
// C# program to find the element // occurring odd number of timesusing System; class GFG{ // Function to find the element // occurring odd number of times static int getOddOccurrence(int []arr, int arr_size) { for (int i = 0; i < arr_size; i++) { int count = 0; for (int j = 0; j < arr_size; j++) { if (arr[i] == arr[j]) count++; } if (count % 2 != 0) return arr[i]; } return -1; } // Driver code public static void Main() { int []arr = { 2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2 }; int n = arr.Length; Console.Write(getOddOccurrence(arr, n)); }} // This code is contributed by Sam007 |
PHP
<?php// PHP program to find the // element occurring odd// number of times // Function to find the element // occurring odd number of timesfunction getOddOccurrence(&$arr, $arr_size){ $count = 0; for ($i = 0; $i < $arr_size; $i++) { for ($j = 0; $j < $arr_size; $j++) { if ($arr[$i] == $arr[$j]) $count++; } if ($count % 2 != 0) return $arr[$i]; } return -1;} // Driver code$arr = array(2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2);$n = sizeof($arr); // Function callingecho(getOddOccurrence($arr, $n)); // This code is contributed// by Shivi_Aggarwal?> |
Javascript
<script> // Javascript program to find the element // occurring odd number of times // Function to find the element // occurring odd number of times function getOddOccurrence(arr, arr_size) { for (let i = 0; i < arr_size; i++) { let count = 0; for (let j = 0; j < arr_size; j++) { if (arr[i] == arr[j]) count++; } if (count % 2 != 0) return arr[i]; } return -1; } // driver code let arr = [ 2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2 ]; let n = arr.length; // Function calling document.write(getOddOccurrence(arr, n)); // This code is contributed by Mayank Tyagi </script> |
Output :
5
Time Complexity: O(n^2)
Auxiliary Space: O(1)
A Better Solution is to use Hashing. Use array elements as a key and their counts as values. Create an empty hash table. One by one traverse the given array elements and store counts. The time complexity of this solution is O(n). But it requires extra space for hashing.
Program :
C++
// C++ program to find the element // occurring odd number of times #include <bits/stdc++.h>using namespace std; // function to find the element // occurring odd number of times int getOddOccurrence(int arr[],int size){ // Defining HashMap in C++ unordered_map<int, int> hash; // Putting all elements into the HashMap for(int i = 0; i < size; i++) { hash[arr[i]]++; } // Iterate through HashMap to check an element // occurring odd number of times and return it for(auto i : hash) { if(i.second % 2 != 0) { return i.first; } } return -1;} // Driver codeint main() { int arr[] = { 2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2 }; int n = sizeof(arr) / sizeof(arr[0]); // Function calling cout << getOddOccurrence(arr, n); return 0; } // This code is contributed by codeMan_d. |
Java
// Java program to find the element occurring odd // number of timesimport java.io.*;import java.util.HashMap; class OddOccurrence { // function to find the element occurring odd // number of times static int getOddOccurrence(int arr[], int n) { HashMap<Integer,Integer> hmap = new HashMap<>(); // Putting all elements into the HashMap for(int i = 0; i < n; i++) { if(hmap.containsKey(arr[i])) { int val = hmap.get(arr[i]); // If array element is already present then // increase the count of that element. hmap.put(arr[i], val + 1); } else // if array element is not present then put // element into the HashMap and initialize // the count to one. hmap.put(arr[i], 1); } // Checking for odd occurrence of each element present // in the HashMap for(Integer a:hmap.keySet()) { if(hmap.get(a) % 2 != 0) return a; } return -1; } // driver code public static void main(String[] args) { int arr[] = new int[]{2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2}; int n = arr.length; System.out.println(getOddOccurrence(arr, n)); }}// This code is contributed by Kamal Rawal |
Python3
# Python3 program to find the element # occurring odd number of times # function to find the element # occurring odd number of times def getOddOccurrence(arr,size): # Defining HashMap in C++ Hash=dict() # Putting all elements into the HashMap for i in range(size): Hash[arr[i]]=Hash.get(arr[i],0) + 1; # Iterate through HashMap to check an element # occurring odd number of times and return it for i in Hash: if(Hash[i]% 2 != 0): return i return -1 # Driver codearr=[2, 3, 5, 4, 5, 2, 4,3, 5, 2, 4, 4, 2]n = len(arr) # Function calling print(getOddOccurrence(arr, n)) # This code is contributed by mohit kumar |
C#
// C# program to find the element occurring odd // number of timesusing System;using System.Collections.Generic; public class OddOccurrence { // function to find the element occurring odd // number of times static int getOddOccurrence(int []arr, int n) { Dictionary<int,int> hmap = new Dictionary<int,int>(); // Putting all elements into the HashMap for(int i = 0; i < n; i++) { if(hmap.ContainsKey(arr[i])) { int val = hmap[arr[i]]; // If array element is already present then // increase the count of that element. hmap.Remove(arr[i]); hmap.Add(arr[i], val + 1); } else // if array element is not present then put // element into the HashMap and initialize // the count to one. hmap.Add(arr[i], 1); } // Checking for odd occurrence of each element present // in the HashMap foreach(KeyValuePair<int, int> entry in hmap) { if(entry.Value % 2 != 0) { return entry.Key; } } return -1; } // Driver code public static void Main(String[] args) { int []arr = new int[]{2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2}; int n = arr.Length; Console.WriteLine(getOddOccurrence(arr, n)); }} // This code is contributed by Princi Singh |
Javascript
<script>// Javascript program to find the element occurring odd// number of times // function to find the element occurring odd // number of times function getOddOccurrence(arr,n) { let hmap = new Map(); // Putting all elements into the HashMap for(let i = 0; i < n; i++) { if(hmap.has(arr[i])) { let val = hmap.get(arr[i]); // If array element is already present then // increase the count of that element. hmap.set(arr[i], val + 1); } else { // if array element is not present then put // element into the HashMap and initialize // the count to one. hmap.set(arr[i], 1); } } // Checking for odd occurrence of each element present // in the HashMap for(let [key, value] of hmap.entries()) { //document.write(hmap[a]+"<br>") if(hmap.get(key) % 2 != 0) return key; } return -1; } // driver code let arr=[2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2]; let n = arr.length; document.write(getOddOccurrence(arr, n)); // This code is contributed by unknown2108</script> |
Output :
5
Time Complexity: O(n)
Auxiliary Space: O(n)
The Best Solution is to do bitwise XOR of all the elements. XOR of all elements gives us odd occurring elements.
Here ^ is the XOR operators; Note : x^0 = x x^y=y^x (Commutative property holds) (x^y)^z = x^(y^z) (Distributive property holds) x^x=0
Below is the implementation of the above approach.
C++
// C++ program to find the element// occurring odd number of times#include <bits/stdc++.h>using namespace std; // Function to find element occurring// odd number of timesint getOddOccurrence(int ar[], int ar_size){ int res = 0; for (int i = 0; i < ar_size; i++) res = res ^ ar[i]; return res;} /* Driver function to test above function */int main(){ int ar[] = {2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2}; int n = sizeof(ar)/sizeof(ar[0]); // Function calling cout << getOddOccurrence(ar, n); return 0;} |
C
// C program to find the element// occurring odd number of times#include <stdio.h> // Function to find element occurring// odd number of timesint getOddOccurrence(int ar[], int ar_size){ int res = 0; for (int i = 0; i < ar_size; i++) res = res ^ ar[i]; return res;} /* Driver function to test above function */int main(){ int ar[] = {2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2}; int n = sizeof(ar) / sizeof(ar[0]); // Function calling printf("%d", getOddOccurrence(ar, n)); return 0;} |
Java
//Java program to find the element occurring odd number of times class OddOccurrence { int getOddOccurrence(int ar[], int ar_size) { int i; int res = 0; for (i = 0; i < ar_size; i++) { res = res ^ ar[i]; } return res; } public static void main(String[] args) { OddOccurrence occur = new OddOccurrence(); int ar[] = new int[]{2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2}; int n = ar.length; System.out.println(occur.getOddOccurrence(ar, n)); }}// This code has been contributed by Mayank Jaiswal |
Python3
# Python program to find the element occurring odd number of times def getOddOccurrence(arr): # Initialize result res = 0 # Traverse the array for element in arr: # XOR with the result res = res ^ element return res # Test arrayarr = [ 2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2] print("%d" % getOddOccurrence(arr)) |
C#
// C# program to find the element// occurring odd number of timesusing System; class GFG{ // Function to find the element // occurring odd number of times static int getOddOccurrence(int []arr, int arr_size) { int res = 0; for (int i = 0; i < arr_size; i++) { res = res ^ arr[i]; } return res; } // Driver code public static void Main() { int []arr = { 2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2 }; int n = arr.Length; Console.Write(getOddOccurrence(arr, n)); }} // This code is contributed by Sam007 |
PHP
<?php// PHP program to find the // element occurring odd // number of times // Function to find element // occurring odd number of timesfunction getOddOccurrence(&$ar, $ar_size){ $res = 0; for ($i = 0; $i < $ar_size; $i++) $res = $res ^ $ar[$i]; return $res;} // Driver Code$ar = array(2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2);$n = sizeof($ar); // Function callingecho(getOddOccurrence($ar, $n)); // This code is contributed // by Shivi_Aggarwal?> |
Javascript
<script> // JavaScript program to find the element // occurring odd number of times // Function to find the element // occurring odd number of times function getOddOccurrence( ar, ar_size){ let res = 0; for (let i = 0; i < ar_size; i++) res = res ^ ar[i]; return res;} // driver code let arr = [ 2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2 ]; let n = arr.length; // Function calling document.write(getOddOccurrence(arr, n)); </script> |
Output :
5
Time Complexity: O(n)
Auxiliary Space: O(1)
Method 3:Using Built-in Python functions:
- Count the frequencies of every element using the Counter function
- Traverse in frequency dictionary
- Check which element has an odd frequency.
- Print that element and break the loop
Below is the implementation:
C++
// C++ code for the above approach#include <iostream>#include <unordered_map>using namespace std; // C++ implementation to find // odd frequency elementint oddElement(int arr[], int n) { // Calculating frequencies using unordered_map unordered_map<int, int> count_map; for (int i = 0; i < n; i++) { count_map[arr[i]]++; } for (int i = 0; i < n; i++) { // If count of element is odd we return if (count_map[arr[i]] % 2 != 0) { return arr[i]; } }} int main() { int arr[] = {1, 1, 3, 3, 5, 6, 6}; int n = sizeof(arr) / sizeof(arr[0]); cout << oddElement(arr, n); return 0;} // This code is contributed by Potta Lokesh |
Java
import java.util.*; public class GFG { public static void main(String[] args) { int[] arr = new int[]{1, 1, 3, 3, 5, 6, 6}; // Creating a HashMap to store the frequencies Map<Integer, Integer> countMap = new HashMap<>(); // Calculating frequencies using HashMap for (int i = 0; i < arr.length; i++) { if (countMap.containsKey(arr[i])) { countMap.put(arr[i], countMap.get(arr[i]) + 1); } else { countMap.put(arr[i], 1); } } // Iterating through the array to find the element with odd frequency for (int i = 0; i < arr.length; i++) { if (countMap.get(arr[i]) % 2 != 0) { System.out.println(arr[i]); return; } } }} // This code is contributed by phasing17 |
Python3
# importing counter from collectionsfrom collections import Counter # Python3 implementation to find # odd frequency elementdef oddElement(arr, n): # Calculating frequencies using Counter count_map = Counter(arr) for i in range(0, n): # If count of element is odd we return if (count_map[arr[i]] % 2 != 0): return arr[i] # Driver Codeif __name__ == "__main__": arr = [1, 1, 3, 3, 5, 6, 6] n = len(arr) print(oddElement(arr, n)) # This code is contributed by vikkycirus |
C#
// C# code to implement the approach using System;using System.Linq;using System.Collections.Generic; class GFG { // to find // odd frequency element static int oddElement(int[] arr, int n) { // Calculating frequencies using unordered_map Dictionary<int, int> count_map=new Dictionary<int,int>(); for (int i = 0; i < n; i++) { if (count_map.ContainsKey(arr[i])) { var val = count_map[arr[i]]; count_map.Remove(arr[i]); count_map.Add(arr[i], val + 1); } else { count_map.Add(arr[i], 1); } } for (int i = 0; i < n; i++) { // If count of element is odd we return if (count_map[arr[i]] % 2 != 0) { return arr[i]; } } return -1; } static public void Main() { int[] arr = {1, 1, 3, 3, 5, 6, 6}; int n = arr.Length; Console.Write(oddElement(arr, n)); }} // This code is contributed by ratiagrawal. |
Javascript
// Javascript code for the above approachconst countMap = new Map(); // JavaScript implementation to find // odd frequency elementfunction oddElement(arr) { // Calculating frequencies using Map for (let i = 0; i < arr.length; i++) { if (countMap.has(arr[i])) { countMap.set(arr[i], countMap.get(arr[i]) + 1); } else { countMap.set(arr[i], 1); } } // Iterating through the array to find the element with odd frequency for (let i = 0; i < arr.length; i++) { if (countMap.get(arr[i]) % 2 != 0) { return arr[i]; } }} // Driver Codeconst arr = [1, 1, 3, 3, 5, 6, 6];console.log(oddElement(arr)); // This code is contributed by pradeepkumarppk2003 |
Output:
5
Time Complexity: O(N)
Auxiliary Space: O(N)
Method 4:Using HashSet
This problem can also be solved using HashSet by traversing the array and inserting element if not already present else deleting the element from the HashSet. So, after the traversal is complete the only element left in the HashSet is the element which is present three times.
C++
// C++ program to find the element// occurring odd number of times#include<bits/stdc++.h>using namespace std; // Function to find the element// occurring odd number of timesint getOddOccurrence(int arr[], int N){ unordered_set<int> s; for(int i=0; i<N; i++){ if(s.find(arr[i]) != s.end()){ s.erase(arr[i]); }else{ s.insert(arr[i]); } } return *(s.begin());} // driver codeint main(){ int arr[] = { 2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2 }; int n = sizeof(arr) / sizeof(arr[0]); // Function calling cout << getOddOccurrence(arr, n); return 0;}; |
Java
/*package whatever //do not write package name here */ // Java program to find the element// occurring odd number of timesimport java.io.*;import java.util.*; class GFG { public static int getOddOccurrence(int arr[], int N) { HashSet<Integer> s = new HashSet<>(); for (int i = 0; i < N; i++) { if (s.contains(arr[i])) { s.remove(arr[i]); } else { s.add(arr[i]); } } int ans = 0; for (int val : s) { ans = val; break; } return ans; } public static void main(String[] args) { int arr[] = { 2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2 }; int n = arr.length; // Function calling System.out.println(getOddOccurrence(arr, n)); }} |
Python3
# Python3 program to find the element# occurring odd number of times # Function to find the element# occurring odd number of timesdef getOddOccurrence(arr, N): s = set() for i in range(N): if arr[i] in s: s.remove(arr[i]); else: s.add(arr[i]); return s # driver codearr = [ 2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2 ];n = len(arr); # Function callingprint(*getOddOccurrence(arr, n)); # This code is contributed by phasing17. |
C#
// C# program to find the element// occurring odd number of times using System;using System.Collections.Generic; class GFG { public static int getOddOccurrence(int[] arr, int N) { HashSet<int> s = new HashSet<int>(); for (int i = 0; i < N; i++) { if (s.Contains(arr[i])) { s.Remove(arr[i]); } else { s.Add(arr[i]); } } int ans = 0; foreach (int val in s) { ans = val; break; } return ans; } public static void Main(string[] args) { int[] arr = { 2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2 }; int n = arr.Length; // Function calling Console.WriteLine(getOddOccurrence(arr, n)); }} |
Javascript
// JS program to find the element// occurring odd number of times // Function to find the element// occurring odd number of timesfunction getOddOccurrence(arr, N){ let s = new Set(); for(var i=0; i<N; i++){ if(s.has(arr[i])){ s.delete(arr[i]); }else{ s.add(arr[i]); } } return Array.from(s).pop();} // driver codelet arr = [ 2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2 ];let n = arr.length; // Function callingconsole.log(getOddOccurrence(arr, n)); // This code is contributed by phasing17. |
Output
5
Time Complexity: O(N)
Auxiliary Space: O(N)
Method 5 (Using binary search) :First sort the array for binary search function . Then we can find frequency of all array elements using lower_bound and upper bound . If frequency is odd then print that element .
Below is the implementation of above approach:
C++
// C++ implementation of the above approach #include <bits/stdc++.h>using namespace std; // Function to find element that occurs // odd times in the array int getOddOccurrence(int arr[], int n){ int count = 0 , ans = -1; sort(arr,arr+n);//sort array for binary search for(int i = 0 ; i < n ;i++) { //index of first and last occ of arr[i] int first_index = lower_bound(arr,arr+n,arr[i])- arr; int last_index = upper_bound(arr,arr+n,arr[i])- arr-1; i = last_index; // assign i to last_index to avoid printing // same element multiple time int fre = last_index-first_index+1;//finding frequency //( occurrences of arr[i] in the array ) if(fre % 2 != 0) { // if element occurs odd times then add that elements to our answer ans = arr[i]; } } return ans;} // Drive codeint main(){ int arr[] = { 2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call cout << getOddOccurrence(arr, n); return 0;} // This Approach is contributed by nikhilsainiofficial546 |
Java
import java.util.Arrays; public class Main { // Function to find element that occurs // odd times in the array static int getOddOccurrence(int arr[], int n) { int count = 0, ans = -1; Arrays.sort(arr); // sort array for binary search for (int i = 0; i < n; i++) { // index of first and last occ of arr[i] int firstIndex = Arrays.binarySearch(arr, arr[i]); int lastIndex = firstIndex + (arr.length - 1 - arr[firstIndex]); i = lastIndex; // assign i to lastIndex to avoid // printing // same element multiple time int fre = lastIndex - firstIndex + 1; // finding frequency // (occurrences of arr[i] in the array) if (fre % 2 != 0) { // if element occurs odd times then add that // elements to our answer ans = arr[i]; } } return ans; } // Driver code public static void main(String[] args) { int arr[] = { 2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2 }; int n = arr.length; // Function call System.out.println(getOddOccurrence(arr, n)); }} |
Python3
# Python implementation of the above approachfrom bisect import bisect_left, bisect_right # Function to find element that occurs# odd times in the arraydef getOddOccurrence(arr, n): ans = -1 arr.sort() # sort array for binary search i = 0 while i < n: # index of first and last occ of arr[i] first_index = bisect_left(arr, arr[i]) last_index = bisect_right(arr, arr[i]) i = last_index # assign i to last_index to avoid printing # same element multiple times fre = last_index - first_index + 1 # finding frequency # (occurrences of arr[i] in the array) if fre % 2 != 0: # if element occurs odd times then add that elements to our answer ans = arr[i] return ans # Driver codearr = [2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2]n = len(arr) # Function callprint(getOddOccurrence(arr, n)) # This code is contributed by phasing17 |
Javascript
function getOddOccurrence(arr) { let count = 0, ans = -1; arr.sort((a, b) => a - b); // sort array for binary search for (let i = 0; i < arr.length; i++) { // index of first and last occ of arr[i] let firstIndex = arr.indexOf(arr[i]); let lastIndex = arr.lastIndexOf(arr[i]); i = lastIndex; // assign i to lastIndex to avoid printing // same element multiple time let fre = lastIndex - firstIndex + 1; // finding frequency // (occurrences of arr[i] in the array) if (fre % 2 != 0) { // if element occurs odd times then add that elements to our answer ans = arr[i]; } } return ans;} // Driver codelet arr = [2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2];console.log(getOddOccurrence(arr)); |
C#
using System;using System.Linq; public class MainClass{// Function to find element that occurs// odd times in the arraystatic int GetOddOccurrence(int[] arr, int n){int count = 0, ans = -1;Array.Sort(arr); // sort array for binary search for (int i = 0; i < n; i++) { // index of first and last occ of arr[i] int firstIndex = Array.BinarySearch(arr, arr[i]); int lastIndex = firstIndex + (arr.Length - 1 - arr[firstIndex]); i = lastIndex; // assign i to lastIndex to avoid // printing // same element multiple time int fre = lastIndex - firstIndex + 1; // finding frequency // (occurrences of arr[i] in the array) if (fre % 2 != 0) { // if element occurs odd times then add that // elements to our answer ans = arr[i]; } } return ans;} // Driver codepublic static void Main(string[] args){ int[] arr = { 2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2 }; int n = arr.Length; // Function call Console.WriteLine(GetOddOccurrence(arr, n));}} |
Output
5
Time Complexity: O(N*Log2N)
Auxiliary Space: O(1)
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.