Find the Two Numbers Appearing Odd Number of Times

Easy15–20 min

Topics

Bit ManipulationXOR

Companies

AmazonMicrosoftFlipkart

Two values in this array break a pattern the rest all obey: every other number turns up an even number of times — twice, four times, however many — while these two show up an odd number of times each. Track down that pair and hand them back smallest first. A running XOR across the whole array cancels every even-count value down to nothing no matter how many times it repeats, leaving only the XOR of the two odd ones combined. Pulling them apart just needs one bit where they're guaranteed to disagree — using that bit to split the whole array into two independent groups leaves exactly one of the pair standing in each group after XOR-ing within it.

Test Case 1:

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

Output:[1, 5]

Explanation:4, 2, and 3 each show up twice; 5 and 1 each show up once — return the odd pair smallest first.

Test Case 2:

Input:nums = [10, 20, 10, 30, 30, 20, 40, 50]

Output:[40, 50]

Explanation:10, 20, and 30 each appear twice; 40 and 50 each appear once.

Test Case 3:

Input:nums = [7, 9]

Output:[7, 9]

Explanation:Just the two odd ones, nothing else to cancel out.

Constraints

◆2 ≤ nums.length ≤ 3 × 10⁴
◆-3 × 10⁴ ≤ nums[i] ≤ 3 × 10⁴
◆Exactly two distinct values in nums occur an odd number of times; every other value occurs an even number of times

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Hashmap Counting

Good

Count how many times every value shows up, using a running tally. Once every value has been tallied, scan the tallies for the two whose count didn't land on an even number — those are the two odd ones out. Sort the pair so the smaller value comes first.

TimeO(n)

SpaceO(n)

Java

Try it out

class Solution {
    public int[] findOddOccurringPair(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }
        List<Integer> oddOnes = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (entry.getValue() % 2 != 0) {
                oddOnes.add(entry.getKey());
            }
        }
        Collections.sort(oddOnes);
        return new int[]{oddOnes.get(0), oddOnes.get(1)};
    }
}

Optimal — XOR Split by Differing Bit

Optimal

A running XOR across the whole array collapses every even-count value to nothing, regardless of how many times it actually repeats, leaving behind the XOR of just the two odd-count values combined. Isolate one bit where those two values must disagree, then split every number into two groups by whether that bit is set — XOR-ing within each group isolates one of the pair per group, since whatever else shares that group still cancels however many times it repeats.