Numbers with odd occurrences

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]

Try it on GfG Practice

Table of Content

[Naive Approach] - O(n^2) time and O(1) space
[Better Approach - 1] Using Sorting - O(n logn) time and O(1) space
[Better Approach - 2] Using Hash Map - O(n) time and O(n) space
[Expected Approach] Using Bit Manipulation - O(n) time and O(1) space

[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;
}

Java

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]);
    }
}

Python

# 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]);
    }
}

JavaScript

// 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]);

Output

45 34

[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;
}

Java

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]);
    }
}

Python

# 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]);
    }
}

JavaScript

// 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]);

Output

45 34

[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;
}

Java

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));
    }
}

Python

# 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]);
    }
}

JavaScript

// 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]);

Output

45 34

[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;
}

Java

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));
    }
}

Python

# 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]);
    }
}

JavaScript

// 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]);

Output

45 34

Numbers with odd occurrences

[Naive Approach] - O(n^2) time and O(1) space

[Better Approach - 1] Using Sorting - O(n logn) time and O(1) space

[Better Approach - 2] Using Hash Map - O(n) time and O(n) space

[Expected Approach] Using Bit Manipulation - O(n) time and O(1) space

Explore