Numbers with odd occurrences
Last Updated : 03 Oct, 2025
Given an unsorted array in which all numbers occur an even number of times except two numbers that occur an odd number of times. Return those two numbers.
Examples:
Input: [12, 23, 34, 12, 12, 23, 12, 45]
Output: [34, 45]
Input: [4, 4, 100, 5000, 4, 4, 4, 4, 100, 100]
Output: [100, 5000]
Input: [10, 20]
Output: [10, 20]
[Naive Approach] - O(n^2) time and O(1) space
The idea is to run two nested loops. The outer loop picks an element and the inner loop counts the number of occurrences of the picked element. If the count of occurrences is odd, then append the element to result, while ensuring that one element is only pushed once into result.
C++ #include <iostream> #include<vector> #include<algorithm> using namespace std; // Function to find the two elements // with odd occurrences. vector<int> twoOddNum(vector<int>& arr) { int n = arr.size(); vector<int> ans = {-1, -1}; int index = 0; // Check for each element for (int i=0; i<n; i++) { // Get the count of arr[i] int cnt = 0; for (int j=0; j<n; j++) { if (arr[j]==arr[i]) cnt++; } // If cnt is odd and arr[i] // has not been added to result yet. if (cnt%2==1 && ans[0]!=arr[i] && ans[1]!=arr[i]) { ans[index++] = arr[i]; } } // Return in decreasing order if (ans[0]<ans[1]) swap(ans[0], ans[1]); return ans; } int main() { vector<int> arr = {12, 23, 34, 12, 12, 23, 12, 45}; vector<int> ans = twoOddNum(arr); cout<<ans[0]<<" "<<ans[1]<<endl; return 0; } import java.util.*; class GfG { // Function to find the two elements // with odd occurrences. static int[] twoOddNum(int[] arr) { int n = arr.length; int[] ans = {-1, -1}; int index = 0; // Check for each element for (int i = 0; i < n; i++) { // Get the count of arr[i] int cnt = 0; for (int j = 0; j < n; j++) { if (arr[j] == arr[i]) cnt++; } // If cnt is odd and arr[i] // has not been added to result yet. if (cnt % 2 == 1 && ans[0] != arr[i] && ans[1] != arr[i]) { ans[index++] = arr[i]; } } // Return in decreasing order if (ans[0] < ans[1]) { int temp = ans[0]; ans[0] = ans[1]; ans[1] = temp; } return ans; } public static void main(String[] args) { int[] arr = {12, 23, 34, 12, 12, 23, 12, 45}; int[] ans = twoOddNum(arr); System.out.println(ans[0] + " " + ans[1]); } } # Function to find the two elements # with odd occurrences. def twoOddNum(arr): n = len(arr) ans = [-1, -1] index = 0 # Check for each element for i in range(n): # Get the count of arr[i] cnt = 0 for j in range(n): if arr[j] == arr[i]: cnt += 1 # If cnt is odd and arr[i] # has not been added to result yet. if cnt % 2 == 1 and ans[0] != arr[i] and ans[1] != arr[i]: ans[index] = arr[i] index += 1 # Return in decreasing order if ans[0] < ans[1]: ans[0], ans[1] = ans[1], ans[0] return ans if __name__ == "__main__": arr = [12, 23, 34, 12, 12, 23, 12, 45] ans = twoOddNum(arr) print(ans[0], ans[1])
using System; class GfG { // Function to find the two elements // with odd occurrences. static int[] twoOddNum(int[] arr) { int n = arr.Length; int[] ans = {-1, -1}; int index = 0; // Check for each element for (int i = 0; i < n; i++) { // Get the count of arr[i] int cnt = 0; for (int j = 0; j < n; j++) { if (arr[j] == arr[i]) cnt++; } // If cnt is odd and arr[i] // has not been added to result yet. if (cnt % 2 == 1 && ans[0] != arr[i] && ans[1] != arr[i]) { ans[index++] = arr[i]; } } // Return in decreasing order if (ans[0] < ans[1]) { int temp = ans[0]; ans[0] = ans[1]; ans[1] = temp; } return ans; } static void Main(string[] args) { int[] arr = {12, 23, 34, 12, 12, 23, 12, 45}; int[] ans = twoOddNum(arr); Console.WriteLine(ans[0] + " " + ans[1]); } } // Function to find the two elements // with odd occurrences. function twoOddNum(arr) { let n = arr.length; let ans = [-1, -1]; let index = 0; // Check for each element for (let i = 0; i < n; i++) { // Get the count of arr[i] let cnt = 0; for (let j = 0; j < n; j++) { if (arr[j] == arr[i]) cnt++; } // If cnt is odd and arr[i] // has not been added to result yet. if (cnt % 2 == 1 && ans[0] != arr[i] && ans[1] != arr[i]) { ans[index++] = arr[i]; } } // Return in decreasing order if (ans[0] < ans[1]) { [ans[0], ans[1]] = [ans[1], ans[0]]; } return ans; } // Driver Code let arr = [12, 23, 34, 12, 12, 23, 12, 45]; let ans = twoOddNum(arr); console.log(ans[0], ans[1]); [Better Approach - 1] Using Sorting - O(n logn) time and O(1) space
The idea is to use sorting and then find the frequency of each element in linear time.
C++ #include <iostream> #include <vector> #include <algorithm> using namespace std; // Function to find the two elements // with odd occurrences. vector<int> twoOddNum(vector<int>& arr) { int n = arr.size(); vector<int> ans = {-1, -1}; int index = 0; // Sort the array sort(arr.begin(), arr.end()); // Get count of each element int i = 0; while (i<n) { int val = arr[i]; int cnt = 0; while (i<n && arr[i]==val) { cnt++; i++; } // If count is odd if (cnt%2==1) ans[index++] = val; } // Return in decreasing order if (ans[0]<ans[1]) swap(ans[0], ans[1]); return ans; } int main() { vector<int> arr = {12, 23, 34, 12, 12, 23, 12, 45}; vector<int> ans = twoOddNum(arr); cout<<ans[0]<<" "<<ans[1]<<endl; return 0; } import java.util.Arrays; class GfG { // Function to find the two elements // with odd occurrences. static int[] twoOddNum(int[] arr) { int n = arr.length; int[] ans = {-1, -1}; int index = 0; // Sort the array Arrays.sort(arr); // Get count of each element int i = 0; while (i < n) { int val = arr[i]; int cnt = 0; while (i < n && arr[i] == val) { cnt++; i++; } // If count is odd if (cnt % 2 == 1) ans[index++] = val; } // Return in decreasing order if (ans[0] < ans[1]) { int temp = ans[0]; ans[0] = ans[1]; ans[1] = temp; } return ans; } public static void main(String[] args) { int[] arr = {12, 23, 34, 12, 12, 23, 12, 45}; int[] ans = twoOddNum(arr); System.out.println(ans[0] + " " + ans[1]); } } # Function to find the two elements # with odd occurrences. def twoOddNum(arr): n = len(arr) ans = [-1, -1] index = 0 # Sort the array arr.sort() # Get count of each element i = 0 while i < n: val = arr[i] cnt = 0 while i < n and arr[i] == val: cnt += 1 i += 1 # If count is odd if cnt % 2 == 1: ans[index] = val index += 1 # Return in decreasing order if ans[0] < ans[1]: ans[0], ans[1] = ans[1], ans[0] return ans if __name__ == "__main__": arr = [12, 23, 34, 12, 12, 23, 12, 45] ans = twoOddNum(arr) print(ans[0], ans[1])
using System; using System.Collections.Generic; class GfG { // Function to find the two elements with odd occurrences static List<int> TwoOddNum(List<int> arr) { int n = arr.Count; List<int> ans = new List<int> { -1, -1 }; int index = 0; // Sort the list arr.Sort(); // Get count of each element int i = 0; while (i < n) { int val = arr[i]; int cnt = 0; while (i < n && arr[i] == val) { cnt++; i++; } // If count is odd if (cnt % 2 == 1 && index < 2) ans[index++] = val; } // Return in decreasing order if (ans[0] < ans[1]) { int temp = ans[0]; ans[0] = ans[1]; ans[1] = temp; } return ans; } static void Main(string[] args) { List<int> arr = new List<int> { 12, 23, 34, 12, 12, 23, 12, 45 }; List<int> ans = TwoOddNum(arr); Console.WriteLine(ans[0] + " " + ans[1]); } } // Function to find the two elements // with odd occurrences. function twoOddNum(arr) { let n = arr.length; let ans = [-1, -1]; let index = 0; // Sort the array arr.sort((a, b) => a - b); // Get count of each element let i = 0; while (i < n) { let val = arr[i]; let cnt = 0; while (i < n && arr[i] === val) { cnt++; i++; } // If count is odd if (cnt % 2 === 1) { ans[index++] = val; } } // Return in decreasing order if (ans[0] < ans[1]) { [ans[0], ans[1]] = [ans[1], ans[0]]; } return ans; } // Driver Code let arr = [12, 23, 34, 12, 12, 23, 12, 45]; let ans = twoOddNum(arr); console.log(ans[0], ans[1]); [Better Approach - 2] Using Hash Map - O(n) time and O(n) space
The idea is to use a hash map to store the count of all values. Then iterate through the map and return the values with odd count.
Step by step approach:
- Traverse all elements and insert them in to a hash table. Element is used as key and the frequency is used as the value in the hash table.
- Iterate through the map and append the values with odd count.
C++ // odd occurrences in an unsorted array #include <iostream> #include <vector> #include <unordered_map> using namespace std; // Function to find the two elements // with odd occurrences. vector<int> twoOddNum(vector<int>& arr) { int n = arr.size(); vector<int> ans = {-1, -1}; int index = 0; // Map to store count unordered_map<int,int> cnt; // Count occurrences in array for (int i=0; i<n; i++) { cnt[arr[i]]++; } // Append the values with odd // count to result for (auto p: cnt) { if (p.second%2==1) { ans[index++] = p.first; } } // Return in decreasing order if (ans[0]<ans[1]) swap(ans[0], ans[1]); return ans; } int main() { vector<int> arr = {12, 23, 34, 12, 12, 23, 12, 45}; vector<int> ans = twoOddNum(arr); cout<<ans[0]<<" "<<ans[1]<<endl; return 0; } import java.util.*; class GfG { // Function to find the two elements with odd occurrences static ArrayList<Integer> twoOddNum(ArrayList<Integer> arr) { int n = arr.size(); ArrayList<Integer> ans = new ArrayList<>(Arrays.asList(-1, -1)); int index = 0; // Map to store count HashMap<Integer, Integer> cnt = new HashMap<>(); // Count occurrences in array for (int i = 0; i < n; i++) { cnt.put(arr.get(i), cnt.getOrDefault(arr.get(i), 0) + 1); } // Append the values with odd count to result for (var entry : cnt.entrySet()) { if (entry.getValue() % 2 == 1 && index < 2) { ans.set(index++, entry.getKey()); } } // Return in decreasing order if (ans.get(0) < ans.get(1)) { int temp = ans.get(0); ans.set(0, ans.get(1)); ans.set(1, temp); } return ans; } public static void main(String[] args) { ArrayList<Integer> arr = new ArrayList<>(Arrays.asList( 12, 23, 34, 12, 12, 23, 12, 45)); ArrayList<Integer> ans = twoOddNum(arr); System.out.println(ans.get(0) + " " + ans.get(1)); } } # Function to find the two elements # with odd occurrences. def twoOddNum(arr): n = len(arr) ans = [-1, -1] index = 0 # Map to store count cnt = {} # Count occurrences in array for num in arr: cnt[num] = cnt.get(num, 0) + 1 # Append the values with odd # count to result for key, value in cnt.items(): if value % 2 == 1: ans[index] = key index += 1 # Return in decreasing order if ans[0] < ans[1]: ans[0], ans[1] = ans[1], ans[0] return ans if __name__ == "__main__": arr = [12, 23, 34, 12, 12, 23, 12, 45] ans = twoOddNum(arr) print(ans[0], ans[1]) using System; using System.Collections.Generic; class GfG { // Function to find the two elements with odd occurrences static List<int> TwoOddNum(List<int> arr) { int n = arr.Count; List<int> ans = new List<int> { -1, -1 }; int index = 0; // Dictionary to store count Dictionary<int, int> cnt = new Dictionary<int, int>(); // Count occurrences in list for (int i = 0; i < n; i++) { if (cnt.ContainsKey(arr[i])) { cnt[arr[i]]++; } else { cnt[arr[i]] = 1; } } // Append the values with odd count to result foreach (var entry in cnt) { if (entry.Value % 2 == 1 && index < 2) { ans[index++] = entry.Key; } } // Return in decreasing order if (ans[0] < ans[1]) { int temp = ans[0]; ans[0] = ans[1]; ans[1] = temp; } return ans; } static void Main(string[] args) { List<int> arr = new List<int> { 12, 23, 34, 12, 12, 23, 12, 45 }; List<int> ans = TwoOddNum(arr); Console.WriteLine(ans[0] + " " + ans[1]); } } // odd occurrences in an unsorted array // Function to find the two elements // with odd occurrences. function twoOddNum(arr) { let n = arr.length; let ans = [-1, -1]; let index = 0; // Map to store count let cnt = new Map(); // Count occurrences in array for (let i = 0; i < n; i++) { cnt.set(arr[i], (cnt.get(arr[i]) || 0) + 1); } // Append the values with odd // count to result for (let [key, value] of cnt) { if (value % 2 === 1) { ans[index++] = key; } } // Return in decreasing order if (ans[0] < ans[1]) { [ans[0], ans[1]] = [ans[1], ans[0]]; } return ans; } // Driver Code let arr = [12, 23, 34, 12, 12, 23, 12, 45]; let ans = twoOddNum(arr); console.log(ans[0], ans[1]); [Expected Approach] Using Bit Manipulation - O(n) time and O(1) space
To find the two numbers occurring odd times, we first compute the XOR of all array elements, resulting in x ^ y, because elements occurring even times cancel out. This XOR value tells us where x and y differ. We then find the rightmost set bit in this XOR value to use as a distinguishing filter. Using this bit, we divide the array into two groups: one where this bit is set and one where it is not. Since x and y differ at this bit, they end up in different groups. Finally, by Xoring all elements within each group, even-count elements cancel out, leaving us with x in one group and y in the other. These two unique numbers are then returned in decreasing order.
C++ // odd occurrences in an unsorted array #include <iostream> #include <vector> using namespace std; // Function to find the two elements // with odd occurrences. vector<int> twoOddNum(vector<int>& arr) { int n = arr.size(); // Get the XOR of the two // numbers we need to find int xorVal = 0; for (int i=0; i<n; i++) { xorVal = arr[i] ^ xorVal; } // Get its last set bit xorVal &= -xorVal; vector<int> ans(2, 0); for (int i=0; i<n; i++) { int num = arr[i]; // If bit is not set, it // belongs to first set. if ((num & xorVal) == 0) { ans[0] ^= num; } // If bit is set, it // belongs to 2nd set. else { ans[1] ^= num; } } // Return in decreasing order if (ans[0]<ans[1]) swap(ans[0], ans[1]); return ans; } int main() { vector<int> arr = {12, 23, 34, 12, 12, 23, 12, 45}; vector<int> ans = twoOddNum(arr); cout<<ans[0]<<" "<<ans[1]<<endl; return 0; } import java.util.*; class GfG { // Function to find the two elements with odd occurrences static ArrayList<Integer> twoOddNum(ArrayList<Integer> arr) { int n = arr.size(); // Get the XOR of the two numbers we need to find int xorVal = 0; for (int i = 0; i < n; i++) { xorVal ^= arr.get(i); } // Get its rightmost set bit (differentiating bit) int rightmostSetBit = xorVal & -xorVal; int num1 = 0, num2 = 0; for (int i = 0; i < n; i++) { int num = arr.get(i); // If bit is not set, it belongs to first set if ((num & rightmostSetBit) == 0) { num1 ^= num; } // If bit is set, it belongs to second set else { num2 ^= num; } } // Prepare result list in decreasing order ArrayList<Integer> ans = new ArrayList<>(); if (num1 > num2) { ans.add(num1); ans.add(num2); } else { ans.add(num2); ans.add(num1); } return ans; } public static void main(String[] args) { ArrayList<Integer> arr = new ArrayList<>(Arrays.asList( 12, 23, 34, 12, 12, 23, 12, 45)); ArrayList<Integer> ans = twoOddNum(arr); System.out.println(ans.get(0) + " " + ans.get(1)); } } # odd occurrences in an unsorted array # Function to find the two elements # with odd occurrences. def twoOddNum(arr): n = len(arr) # Get the XOR of the two numbers we need to find xorVal = 0 for num in arr: xorVal ^= num # Get its last set bit xorVal &= -xorVal ans = [0, 0] for num in arr: # If bit is not set, it # belongs to first set. if (num & xorVal) == 0: ans[0] ^= num # If bit is set, it # belongs to 2nd set. else: ans[1] ^= num # Return in decreasing order if ans[0] < ans[1]: ans[0], ans[1] = ans[1], ans[0] return ans if __name__ == "__main__": arr = [12, 23, 34, 12, 12, 23, 12, 45] ans = twoOddNum(arr) print(ans[0], ans[1])
using System; using System.Collections.Generic; class GfG { // Function to find the two elements with odd occurrences static List<int> TwoOddNum(List<int> arr) { int n = arr.Count; // Get the XOR of the two numbers we need to find int xorVal = 0; for (int i = 0; i < n; i++) { xorVal ^= arr[i]; } // Get its rightmost set bit (differentiating bit) int rightmostSetBit = xorVal & -xorVal; int num1 = 0, num2 = 0; for (int i = 0; i < n; i++) { int num = arr[i]; // If bit is not set, it belongs to first set if ((num & rightmostSetBit) == 0) { num1 ^= num; } // If bit is set, it belongs to second set else { num2 ^= num; } } // Prepare result list in decreasing order List<int> ans = new List<int>(); if (num1 > num2) { ans.Add(num1); ans.Add(num2); } else { ans.Add(num2); ans.Add(num1); } return ans; } static void Main(string[] args) { List<int> arr = new List<int> { 12, 23, 34, 12, 12, 23, 12, 45 }; List<int> ans = TwoOddNum(arr); Console.WriteLine(ans[0] + " " + ans[1]); } } // odd occurrences in an unsorted array // Function to find the two elements // with odd occurrences. function twoOddNum(arr) { let n = arr.length; // Get the XOR of the two numbers we need to find let xorVal = 0; for (let i = 0; i < n; i++) { xorVal = arr[i] ^ xorVal; } // Get its last set bit xorVal &= -xorVal; let ans = [0, 0]; for (let i = 0; i < n; i++) { let num = arr[i]; // If bit is not set, it // belongs to first set. if ((num & xorVal) === 0) { ans[0] ^= num; } // If bit is set, it // belongs to 2nd set. else { ans[1] ^= num; } } // Return in decreasing order if (ans[0] < ans[1]) { [ans[0], ans[1]] = [ans[1], ans[0]]; } return ans; } // Driver Code let arr = [12, 23, 34, 12, 12, 23, 12, 45]; let ans = twoOddNum(arr); console.log(ans[0], ans[1]);
Explore
DSA Fundamentals
Data Structures
Algorithms
Advanced
Interview Preparation
Practice Problem
My Profile