Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Two odd Occuring Numbers in an Array

MEDIUMProblemSolveExternal Links

Description

Given an unsorted array of positive integers where every number appears an even number of times except for exactly two numbers that each appear an odd number of times, find and return those two numbers.

The result should be returned in decreasing order (larger number first).

For example, if the array is [4, 2, 4, 5, 2, 3, 3, 1], the numbers 4, 2, and 3 each appear twice (even), while 5 appears once and 1 appears once (both odd). So the answer is [5, 1].

Examples

Example 1

Input: arr = [4, 2, 4, 5, 2, 3, 3, 1]

Output: [5, 1]

Explanation: Count the occurrences — 4 appears 2 times, 2 appears 2 times, 3 appears 2 times, 5 appears 1 time, and 1 appears 1 time. The two numbers with odd occurrences are 5 and 1. Returned in decreasing order: [5, 1].

Example 2

Input: arr = [1, 7, 5, 7, 5, 4, 7, 4]

Output: [7, 1]

Explanation: 7 appears 3 times (odd), 5 appears 2 times (even), 4 appears 2 times (even), and 1 appears 1 time (odd). The two numbers with odd occurrences are 7 and 1. In decreasing order: [7, 1].

Example 3

Input: arr = [4, 4, 100, 5000, 4, 4, 4, 4, 100, 100]

Output: [5000, 100]

Explanation: 4 appears 6 times (even), 100 appears 3 times (odd), 5000 appears 1 time (odd). The two odd-occurring numbers are 5000 and 100. In decreasing order: [5000, 100].

Constraints

  • 2 ≤ arr.size() ≤ 10^6
  • 1 ≤ arr[i] ≤ 10^7
  • Exactly two distinct numbers have odd occurrences; all others have even occurrences

Editorial

Brute Force

Intuition

The most straightforward way to find the two numbers with odd occurrences is to count how many times each number appears and then check which counts are odd.

For every element in the array, we scan the entire array to count how many times that element occurs. If the count is odd and we haven't already recorded that element, we add it to our result.

Think of it like a roll call at a crowded event. For each person's name you hear, you walk through the entire guest list to count how many times that name appears. If you find a name that appears an odd number of times, you write it down. It works, but it requires walking through the whole list for every single name — very repetitive work.

Step-by-Step Explanation

Let's trace through with arr = [4, 2, 4, 5, 2, 3, 3, 1]:

Step 1: Pick arr[0] = 4. Count occurrences of 4 in the entire array: indices 0 and 2 → count = 2 (even). Skip.

Step 2: Pick arr[1] = 2. Count occurrences of 2: indices 1 and 4 → count = 2 (even). Skip.

Step 3: Pick arr[2] = 4. Same as step 1 — already counted, count = 2 (even). Skip.

Step 4: Pick arr[3] = 5. Count occurrences of 5: only index 3 → count = 1 (odd). Add 5 to result. Result = [5].

Step 5: Pick arr[4] = 2. Already counted, count = 2 (even). Skip.

Step 6: Pick arr[5] = 3. Count occurrences of 3: indices 5 and 6 → count = 2 (even). Skip.

Step 7: Pick arr[6] = 3. Same as step 6 — count = 2 (even). Skip.

Step 8: Pick arr[7] = 1. Count occurrences of 1: only index 7 → count = 1 (odd). Add 1 to result. Result = [5, 1].

Step 9: Sort result in decreasing order: [5, 1] (already sorted). Return [5, 1].

Algorithm

  1. Initialize an empty result list
  2. For each element arr[i] in the array:
    a. Count how many times arr[i] appears in the entire array (inner loop)
    b. If the count is odd AND arr[i] is not already in the result, add it
  3. Return the result sorted in decreasing order

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> twoOddNum(vector<int>& arr) {
        int n = arr.size();
        vector<int> ans;
        
        for (int i = 0; i < n; i++) {
            int cnt = 0;
            for (int j = 0; j < n; j++) {
                if (arr[j] == arr[i]) cnt++;
            }
            // Add if odd count and not already in result
            if (cnt % 2 == 1) {
                bool found = false;
                for (int k = 0; k < ans.size(); k++) {
                    if (ans[k] == arr[i]) { found = true; break; }
                }
                if (!found) ans.push_back(arr[i]);
            }
        }
        
        // Return in decreasing order
        if (ans[0] < ans[1]) swap(ans[0], ans[1]);
        return ans;
    }
};
class Solution:
    def twoOddNum(self, arr):
        n = len(arr)
        ans = []
        
        for i in range(n):
            cnt = 0
            for j in range(n):
                if arr[j] == arr[i]:
                    cnt += 1
            # Add if odd count and not already in result
            if cnt % 2 == 1 and arr[i] not in ans:
                ans.append(arr[i])
        
        # Return in decreasing order
        ans.sort(reverse=True)
        return ans
import java.util.*;

class Solution {
    public int[] twoOddNum(int[] arr) {
        int n = arr.length;
        List<Integer> ans = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            int cnt = 0;
            for (int j = 0; j < n; j++) {
                if (arr[j] == arr[i]) cnt++;
            }
            if (cnt % 2 == 1 && !ans.contains(arr[i])) {
                ans.add(arr[i]);
            }
        }
        
        // Return in decreasing order
        int[] result = new int[2];
        result[0] = Math.max(ans.get(0), ans.get(1));
        result[1] = Math.min(ans.get(0), ans.get(1));
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n²)

For each of the n elements, we scan the entire array of n elements to count occurrences. This gives us n × n = n² comparisons in the worst case. With n up to 10^6, this would require up to 10^12 operations — far too slow.

Space Complexity: O(1)

We only use a fixed-size result list (at most 2 elements) and a few counter variables. No data structures that grow with input size.

Why This Approach Is Not Efficient

The brute force counts every element's frequency from scratch using an inner loop, leading to O(n²) time. With n up to 10^6, this means up to 10^12 operations — which would take hundreds of seconds, far exceeding typical time limits.

The core waste: we recount the same element multiple times. If 4 appears at indices 0 and 2, we count all occurrences of 4 when processing index 0, and then again when processing index 2 — doing identical work twice.

The fix is obvious: remember the counts. If we use a hash map to store each element's frequency in a single pass, we eliminate all redundant counting. One pass to count (O(n)), one pass to find odd counts (O(n)) = O(n) total. The trade-off is O(n) extra space for the map.

Better Approach - Hash Map Frequency Count

Intuition

Instead of recounting from scratch each time, we can count every element's frequency in a single pass using a hash map, then scan the map to find the two elements with odd counts.

Think of it like taking attendance with a tally sheet. You walk through the crowd once, making a tally mark next to each person's name. After the single walk-through, you look at the sheet and immediately see which names have an odd number of tally marks. No re-scanning required.

This trades space (the tally sheet / hash map) for a massive time improvement: from O(n²) down to O(n).

Step-by-Step Explanation

Let's trace through with arr = [4, 2, 4, 5, 2, 3, 3, 1]:

Step 1: Initialize empty hash map.

Step 2: Process 4 → map: {4: 1}.

Step 3: Process 2 → map: {4: 1, 2: 1}.

Step 4: Process 4 → map: {4: 2, 2: 1}.

Step 5: Process 5 → map: {4: 2, 2: 1, 5: 1}.

Step 6: Process 2 → map: {4: 2, 2: 2, 5: 1}.

Step 7: Process 3 → map: {4: 2, 2: 2, 5: 1, 3: 1}.

Step 8: Process 3 → map: {4: 2, 2: 2, 5: 1, 3: 2}.

Step 9: Process 1 → map: {4: 2, 2: 2, 5: 1, 3: 2, 1: 1}.

Step 10: Scan the map for odd counts:

  • 4: count 2 (even) — skip
  • 2: count 2 (even) — skip
  • 5: count 1 (odd) — add to result
  • 3: count 2 (even) — skip
  • 1: count 1 (odd) — add to result

Step 11: Result = [5, 1]. Already in decreasing order. Return [5, 1].

Hash Map Frequency Count — Building and Scanning — Watch how we build a frequency map in a single pass, then scan it to find the two elements with odd counts.

Algorithm

  1. Create an empty hash map to store frequencies
  2. Iterate through the array, incrementing the count for each element
  3. Iterate through the hash map entries
  4. For each entry with an odd count, add the key to the result
  5. Return the result sorted in decreasing order

Code

#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> twoOddNum(vector<int>& arr) {
        unordered_map<int, int> freq;
        for (int num : arr) {
            freq[num]++;
        }
        
        vector<int> ans;
        for (auto& [key, count] : freq) {
            if (count % 2 == 1) {
                ans.push_back(key);
            }
        }
        
        // Return in decreasing order
        if (ans[0] < ans[1]) swap(ans[0], ans[1]);
        return ans;
    }
};
from collections import Counter

class Solution:
    def twoOddNum(self, arr):
        freq = Counter(arr)
        ans = [key for key, count in freq.items() if count % 2 == 1]
        ans.sort(reverse=True)
        return ans
import java.util.*;

class Solution {
    public int[] twoOddNum(int[] arr) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : arr) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        
        int[] ans = new int[2];
        int idx = 0;
        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            if (entry.getValue() % 2 == 1) {
                ans[idx++] = entry.getKey();
            }
        }
        
        // Return in decreasing order
        if (ans[0] < ans[1]) {
            int temp = ans[0];
            ans[0] = ans[1];
            ans[1] = temp;
        }
        return ans;
    }
}

Complexity Analysis

Time Complexity: O(n)

We make two linear passes: one through the array of n elements to build the frequency map (each insertion/update is O(1) amortized), and one through the map entries (at most n entries) to find odd counts. Total: O(n) + O(n) = O(n).

Space Complexity: O(n)

In the worst case, all n elements are distinct, so the hash map stores n key-value pairs. This O(n) extra space is the trade-off we made to bring time down from O(n²) to O(n).

But can we do better on space? The hash map uses O(n) memory. For very large arrays (n up to 10^6), this is significant. Is there a way to find the two odd-occurring numbers in O(n) time using only O(1) space? Bit manipulation provides exactly that.

Why This Approach Is Not Efficient

The hash map approach achieves O(n) time, which is optimal since we must read every element at least once. However, it uses O(n) extra space for the frequency map.

For arrays with up to 10^6 elements and values up to 10^7, the hash map could consume several megabytes of memory. In memory-constrained environments or competitive programming with strict memory limits, this matters.

The key insight that enables an O(1) space solution comes from a powerful property of XOR:

  • x ⊕ x = 0 — XOR of any number with itself is 0
  • x ⊕ 0 = x — XOR of any number with 0 is itself

This means if we XOR all elements, numbers appearing an even number of times cancel out completely, leaving only the XOR of the two odd-occurring numbers. With one more clever trick — splitting elements by a distinguishing bit — we can isolate each number individually, all in O(1) space.

Optimal Approach - XOR Bit Manipulation

Intuition

This approach leverages two key XOR properties:

  1. XOR cancels duplicates: When you XOR a number with itself, the result is 0. So if we XOR all elements in the array, every number appearing an even number of times cancels out. What remains is x ⊕ y, where x and y are the two odd-occurring numbers.

  2. A set bit means x and y differ there: Since x ≠ y, their XOR must have at least one bit set to 1. Any set bit in x ⊕ y represents a position where x and y have different bit values — one has 0 and the other has 1 at that position.

Here's the clever part: we pick any set bit (typically the rightmost one for simplicity) from x ⊕ y and use it to split all array elements into two groups:

  • Group A: elements where that bit is 0
  • Group B: elements where that bit is 1

Since x and y differ at this bit, they are guaranteed to land in different groups. And since every even-occurring number has all its copies in the same group (same value = same bits), they still cancel out within their group.

So XOR-ing all elements in Group A gives us one of the two numbers, and XOR-ing all elements in Group B gives us the other.

Step-by-Step Explanation

Let's trace through with arr = [4, 2, 4, 5, 2, 3, 3, 1]:

The two odd-occurring numbers are x = 5 (binary: 101) and y = 1 (binary: 001).

Phase 1: XOR all elements to get x ⊕ y

Step 1: xorVal = 0. Start XOR-ing all elements.

Step 2: xorVal = 0 ⊕ 4 = 4 (binary: 100).

Step 3: xorVal = 4 ⊕ 2 = 6 (binary: 110).

Step 4: xorVal = 6 ⊕ 4 = 2 (binary: 010). The second 4 cancels the first.

Step 5: xorVal = 2 ⊕ 5 = 7 (binary: 111).

Step 6: xorVal = 7 ⊕ 2 = 5 (binary: 101). The second 2 cancels the first.

Step 7: xorVal = 5 ⊕ 3 = 6 (binary: 110).

Step 8: xorVal = 6 ⊕ 3 = 5 (binary: 101). The second 3 cancels the first.

Step 9: xorVal = 5 ⊕ 1 = 4 (binary: 100). Now xorVal = 5 ⊕ 1 = 4.

Phase 2: Find a distinguishing bit

Step 10: Find the rightmost set bit of xorVal = 4 (binary: 100). The rightmost set bit is at position 2 (value 4). Use xorVal & (-xorVal) = 4 & (-4) = 4. So setBit = 4.

Phase 3: Split and XOR each group

Step 11: Partition all elements by whether bit 2 is set:

  • Group A (bit 2 = 0): 2 (010), 2 (010), 5 (101), 3 (011), 3 (011), 1 (001)
  • Group B (bit 2 = 1): 4 (100), 4 (100)

Wait — let me re-check. setBit = 4 (bit position 2). Check each element:

  • 4 = 100 → bit 2 IS set → Group B
  • 2 = 010 → bit 2 NOT set → Group A
  • 4 = 100 → bit 2 IS set → Group B
  • 5 = 101 → bit 2 IS set → Group B
  • 2 = 010 → bit 2 NOT set → Group A
  • 3 = 011 → bit 2 NOT set → Group A
  • 3 = 011 → bit 2 NOT set → Group A
  • 1 = 001 → bit 2 NOT set → Group A

Group A (bit 2 = 0): [2, 2, 3, 3, 1]
Group B (bit 2 = 1): [4, 4, 5]

Step 12: XOR Group A: 2⊕2⊕3⊕3⊕1 = 0⊕0⊕1 = 1. Found y = 1!

Step 13: XOR Group B: 4⊕4⊕5 = 0⊕5 = 5. Found x = 5!

Step 14: Return in decreasing order: [5, 1].

XOR Bit Manipulation — Three-Phase Algorithm — Watch the three phases: (1) XOR all elements to get x⊕y, (2) find a distinguishing bit, (3) split elements into two groups and XOR each group to isolate the two odd-occurring numbers.

Algorithm

  1. Phase 1 — Get x ⊕ y: XOR all elements in the array. The result is x ⊕ y because all even-occurring elements cancel out.
  2. Phase 2 — Find distinguishing bit: Compute the rightmost set bit of x ⊕ y using xorVal & (-xorVal). This bit position is where x and y differ.
  3. Phase 3 — Split and isolate:
    a. Initialize two variables: num1 = 0, num2 = 0
    b. For each element in the array:
    • If the element has the distinguishing bit set: num2 ^= element
    • Otherwise: num1 ^= element
      c. After the loop, num1 = one odd-occurring number, num2 = the other
  4. Return [num1, num2] in decreasing order

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> twoOddNum(vector<int>& arr) {
        int n = arr.size();
        
        // Phase 1: XOR all elements to get x ^ y
        int xorVal = 0;
        for (int i = 0; i < n; i++) {
            xorVal ^= arr[i];
        }
        
        // Phase 2: Find rightmost set bit
        int setBit = xorVal & (-xorVal);
        
        // Phase 3: Split into two groups and XOR each
        int num1 = 0, num2 = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] & setBit) {
                num2 ^= arr[i];
            } else {
                num1 ^= arr[i];
            }
        }
        
        // Return in decreasing order
        if (num1 < num2) swap(num1, num2);
        return {num1, num2};
    }
};
class Solution:
    def twoOddNum(self, arr):
        # Phase 1: XOR all elements to get x ^ y
        xor_val = 0
        for num in arr:
            xor_val ^= num
        
        # Phase 2: Find rightmost set bit
        set_bit = xor_val & (-xor_val)
        
        # Phase 3: Split into two groups and XOR each
        num1, num2 = 0, 0
        for num in arr:
            if num & set_bit:
                num2 ^= num
            else:
                num1 ^= num
        
        # Return in decreasing order
        return [max(num1, num2), min(num1, num2)]
class Solution {
    public int[] twoOddNum(int[] arr) {
        int n = arr.length;
        
        // Phase 1: XOR all elements to get x ^ y
        int xorVal = 0;
        for (int i = 0; i < n; i++) {
            xorVal ^= arr[i];
        }
        
        // Phase 2: Find rightmost set bit
        int setBit = xorVal & (-xorVal);
        
        // Phase 3: Split into two groups and XOR each
        int num1 = 0, num2 = 0;
        for (int i = 0; i < n; i++) {
            if ((arr[i] & setBit) != 0) {
                num2 ^= arr[i];
            } else {
                num1 ^= arr[i];
            }
        }
        
        // Return in decreasing order
        int[] result = new int[2];
        result[0] = Math.max(num1, num2);
        result[1] = Math.min(num1, num2);
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

We make two passes through the array: one to compute the total XOR (n operations), and one to split elements into groups and XOR each group (n operations). Each operation (XOR, AND) is O(1). Total: O(n) + O(n) = O(n).

Space Complexity: O(1)

We use only a fixed number of integer variables (xorVal, setBit, num1, num2) regardless of input size. No hash maps, no frequency arrays, no additional data structures.

Why this is optimal: We must read every element at least once (any unread element could be one of the answers), so O(n) is a lower bound on time. This solution matches that lower bound. For space, O(1) is the best possible since we need at least a constant number of variables. The XOR bit trick achieves both optimal bounds simultaneously — something the hash map approach could not (it needed O(n) space).