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 times 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 int 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 times class 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 times def 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 times using 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 times function 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 calling echo (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 code int 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 times import 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 code arr = [ 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 times using 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 times int 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 times int 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 array arr = [ 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 times using 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 times function 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 calling echo (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 element int 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 collections from collections import Counter # Python3 implementation to find # odd frequency element def 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 Code if __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 approach const countMap = new Map(); // JavaScript implementation to find // odd frequency element function 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 Code const 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 times int 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 code int 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 times import 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 times def 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 code arr = [ 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 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 times function 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 code let arr = [ 2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2 ]; let n = arr.length; // Function calling console.log(getOddOccurrence(arr, n)); // This code is contributed by phasing17. |
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 code int 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 approach from bisect import bisect_left, bisect_right # Function to find element that occurs # odd times in the array def 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 code arr = [ 2 , 3 , 5 , 4 , 5 , 2 , 4 , 3 , 5 , 2 , 4 , 4 , 2 ] n = len (arr) # Function call print (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 code let 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 array static 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 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 Console.WriteLine(GetOddOccurrence(arr, n)); } } |
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.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!