Find Two Odd-Occurring Elements in an Array

Title: Find Two Odd-Occurring Elements in an Array

An array where every element shows up an even number of times except for exactly two values is a classic interviewer’s favorite, because the obvious hash-map solution works but a neat bitwise trick solves it in a single pass with no extra memory. In this guide, you will learn how to isolate the two odd-occurring values using XOR and a differentiating bit, write a complete Java implementation, trace the algorithm one iteration at a time, and sharpen your intuition with worked examples, common mistakes, and the follow-up questions interviewers like to drill into.

Understanding the Problem

You are given an integer array nums in which every element occurs an even number of times, except for exactly two distinct elements that occur an odd number of times. Return those two elements.

For instance, if nums = {4, 2, 4, 5, 2, 3, 3, 1}, the values 4, 2, and 3 each occur twice, while 5 and 1 each occur once. The answer is 5 and 1, the two odd-occurring values. The order in which you return the pair does not usually matter unless the interviewer asks for it sorted.

The problem is a direct extension of the single-number problem, where only one value occurs an odd number of times. There, a plain XOR of the whole array gives the answer because every even-occurring value cancels itself out. Here, two values survive the cancellation, so a single XOR is not enough on its own; you need one more trick to separate the surviving pair.

Approach Using XOR and a Differentiating Bit

XOR-ing every element of nums cancels every value that occurs an even number of times, leaving xorAll = a ^ b, where a and b are the two odd-occurring values. Since a and b are different, xorAll is never zero, and at least one bit position differs between them. Any bit that is set in xorAll is a bit where exactly one of a or b has a 1, so that bit can split the whole array into two groups, one containing a and one containing b, without ever comparing values directly.

The expression xorAll & -xorAll isolates the rightmost set bit of xorAll. Every even-occurring value either has that bit set in both of its occurrences or clear in both, so it still cancels out inside whichever group it lands in; only a and b end up alone in their respective groups.

Here are the steps:

1. Initialize xorAll = 0 and XOR every element of nums into it.
2. Isolate the rightmost set bit with rightmostSetBit = xorAll & -xorAll.
3. Initialize two accumulators, first = 0 and second = 0.
4. Iterate nums again. If num & rightmostSetBit is nonzero, XOR num into first; otherwise XOR it into second.
5. After the loop, first and second hold the two odd-occurring values.
6. Return first and second as the result.

Java Program to Find Two Odd-Occurring Elements in an Array

Let us put the approach into a complete, compilable Java program:

public class FindTwoOddOccurringElements {

    public static int[] findTwoOdd(int[] nums) {
        int xorAll = 0;
        for (int num : nums) {
            xorAll ^= num;
        }

        int rightmostSetBit = xorAll & -xorAll;

        int first = 0;
        int second = 0;
        for (int num : nums) {
            if ((num & rightmostSetBit) != 0) {
                first ^= num;
            } else {
                second ^= num;
            }
        }

        return new int[] {first, second};
    }

    public static void main(String[] args) {
        int[] nums = {4, 2, 4, 5, 2, 3, 3, 1};
        int[] result = findTwoOdd(nums);
        System.out.println("Odd occurring elements: " + result[0] + ", " + result[1]);
    }
}

Explanation of the Program

• The method findTwoOdd accepts an int[] and returns a two-element int[] holding the odd-occurring values.
• The first for loop builds xorAll, the XOR of every element. Every value that occurs an even number of times XORs with itself an even number of times and vanishes, leaving only a ^ b.
• rightmostSetBit = xorAll & -xorAll uses two’s complement negation to turn off every set bit except the lowest one, giving a single bit position where a and b differ.
• The second for loop partitions every element by that bit. (num & rightmostSetBit) != 0 sends the element to first; otherwise it goes to second.
• Because every even-occurring value lands in the same group on both of its occurrences, it cancels out inside that group. Only a and b are left standing, one in each group.
• main calls the method on a sample input and prints both odd-occurring values in the order the algorithm produces them.

Step-by-Step Trace

Let us walk the partitioning loop through a small fresh input so the bit split is easy to follow. Consider nums = {9, 2, 9, 5, 2, 7}; the target output is 7 and 5, the two odd-occurring values. The first loop gives xorAll = 2, so rightmostSetBit = 2. first and second both start at 0.

At the end of each iteration, first holds the XOR of every value seen so far whose rightmostSetBit bit is set, and second holds the XOR of every value whose bit is clear; because 9 and 2 each appear twice in the same group, they cancel each other out, leaving first = 7 and second = 5.

Examples

Let us look at a few runs that stretch different parts of the algorithm.

Example 1: Negative Values Among the Odd-Occurring Elements

int[] nums = {-3, 4, -3, 7, 4, 9};
int[] result = findTwoOdd(nums);

System.out.println("Odd occurring elements: " + result[0] + ", " + result[1]);
// Output: Odd occurring elements: 7, 9

-3 and 4 each occur twice, while 7 and 9 each occur once. XOR operates on the two’s complement bit pattern regardless of sign, so negative values cancel out exactly like positive ones, and the method still returns the correct pair, 7 and 9.

Example 2: Larger Values With a Repeated Pair on Both Sides

int[] nums = {11, 23, 11, 45, 23, 67, 89, 67};
int[] result = findTwoOdd(nums);

System.out.println("Odd occurring elements: " + result[0] + ", " + result[1]);
// Output: Odd occurring elements: 45, 89

11, 23, and 67 each occur twice, leaving 45 and 89 as the odd-occurring values. The larger magnitudes do not change the algorithm at all; XOR and bitwise AND work identically regardless of how large the values are, as long as they fit in an int.

Example 3: The Smallest Possible Input

int[] nums = {15, 28};
int[] result = findTwoOdd(nums);

System.out.println("Odd occurring elements: " + result[0] + ", " + result[1]);
// Output: Odd occurring elements: 15, 28

With only two elements, both occur exactly once, so both are odd-occurring by definition. xorAll equals 15 ^ 28, and the differentiating bit sends each value to its own group, so the method still works correctly on the smallest valid input.

Common Mistakes to Avoid

Here are the slip-ups learners tend to make when implementing the two-odd-elements trick:

• Returning xorAll as one of the answers – xorAll is a ^ b, not a or b individually; printing it directly gives a value that is not even present in the array. You must run the second partitioning pass to recover a and b separately.
• Isolating the bit with xorAll & (xorAll – 1) – that expression clears the rightmost set bit instead of isolating it, and produces 0 whenever xorAll is a power of two, which collapses the partition into one group. Use xorAll & -xorAll to isolate the bit instead.
• Partitioning by odd or even value instead of by the chosen bit – checking num % 2 confuses an odd-occurring element with an odd-valued element; those are unrelated properties. The split must use num & rightmostSetBit, not the parity of num itself.
• Assuming the pair comes back in sorted order – the algorithm returns first and second in whatever order the bit split happens to produce, which depends on the input order. Sort the pair yourself if the caller expects ascending order.

Additional Considerations

A few points worth remembering about this algorithm:

1. Time complexity: Two linear passes over n elements, so the total running time is O(n).
2. Space complexity: Only a handful of int accumulators are used, so the extra space is O(1).
3. Why negation works for isolating a bit: In two’s complement, -xorAll equals ~xorAll + 1, which flips every bit below the rightmost set bit back to 1 and carries into it; ANDing with the original value leaves only that one bit standing.
4. Relationship to the single-number problem: When only one value occurs an odd number of times, xorAll already is the answer, no partitioning step is needed. The two-value version adds the bit-split pass precisely because one XOR result can no longer represent two distinct unknowns.
5. Alternative with a HashMap: Count occurrences in a HashMap<Integer, Integer> and collect every key whose count is odd. This is O(n) time and O(n) extra space, and it generalizes to any number of odd-occurring values, unlike the bit-split trick.

Edge Cases to Test

Before you declare the implementation done, run it against these boundary inputs:

• Exactly two elements, both occurring once
• Negative values among the odd-occurring elements
• Odd-occurring elements of equal magnitude but opposite sign
• The XOR of the two odd-occurring values landing on bit zero
• Many even-occurring values repeated four or more times
• Integer.MIN_VALUE or Integer.MAX_VALUE present
• A very large array dominated by even-occurring duplicates
• Null array reference

Interview Follow-up Questions

Once the base version works, an interviewer will usually probe deeper with questions like these:

• What if there are three odd-occurring elements instead of two? – a single differentiating bit can only split the array in half, so it cannot isolate three unknowns; fall back to a frequency map and collect every key whose count is odd.
• What if you must return the pair in ascending order? – compare first and second after computing them and swap if first is greater, which costs O(1) extra work.
• What if the input arrives as a one-pass stream of unknown length? – this algorithm fundamentally needs two full passes, so for a true single pass switch to a HashMap<Integer, Integer> that tracks running counts and filters the odd ones once the stream ends.
• What if the array is spread across billions of elements on multiple machines? – XOR is commutative and associative, so each worker can compute a local XOR of its shard; merge the shard results with XOR to get the global xorAll, then re-run the partitioning pass across the shards using the same differentiating bit.

Conclusion

In this guide, we solved the problem of finding the two values in an array that occur an odd number of times. XOR-ing the whole array collapses every even-occurring value down to a ^ b, and isolating a single differentiating bit lets a second pass split the array into two groups that each contain exactly one of the odd-occurring values. The result is an O(n) time, O(1) space solution that needs nothing more than two integer accumulators.

Try adapting the code to return the pair in sorted order, generalize it to a frequency map when the number of odd-occurring values is not known in advance, or verify it against arrays that mix positive and negative values. Happy coding!

You can learn more about Array techniques: Arrays