Find the Only Odd-Occurring Element in an Array

Title: Find the Only Odd-Occurring Element in an Array

Imagine an array where every number shows up an even number of times, except for exactly one number that shows up an odd number of times. Your job is to find that one odd-occurring number, and ideally without using any extra memory to count occurrences. This is a classic Java interview question that tests whether you know the XOR bit trick, and it comes up often as a warm-up before harder bitwise problems.

In this guide, you will learn the XOR-based approach to this problem, walk through a full Java program, trace the algorithm by hand on a concrete input, and work through the mistakes and edge cases that interviewers specifically look for.

Understanding the Problem

You are given an array of integers. Every value in the array occurs an even number of times, except for a single value that occurs an odd number of times. You need to return that single value.

For example, in [1, 1, 2, 2, 3, 2, 2], the value 1 occurs twice, 2 occurs four times, and 3 occurs once. Since 3 is the only value with an odd count, the answer is 3.

A naive approach would count occurrences with a HashMap<Integer, Integer> and then scan for the key whose count is odd. That works, but it needs O(n) extra space. The elegant solution uses the XOR operator to solve the problem in O(n) time and O(1) extra space.

Approach / Algorithm Steps

The key insight is that XOR-ing a number with itself always produces 0, and XOR-ing any number with 0 returns the number unchanged. So if you XOR every element of the array together, every value that appears an even number of times cancels itself out, leaving only the value that appears an odd number of times.

1. Initialize a variable named result to 0.
2. Iterate over every element in the input array exactly once.
3. XOR the current element into result using the ^= operator.
4. Rely on the property that x ^ x = 0, so any value that appears an even number of times cancels itself out by the time the loop finishes.
5. After the loop ends, result holds exactly the value that occurred an odd number of times.
6. Return result as the answer.

Java Program

public class OddOccurrenceFinder {

    public static int findOddOccurrence(int[] arr) {
        int result = 0;
        for (int i = 0; i < arr.length; i++) {
            result ^= arr[i];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {1, 1, 2, 2, 3, 2, 2};
        int odd = findOddOccurrence(arr);
        System.out.println("The odd occurring element is: " + odd);
    }
}

Explanation of the Program

• The method findOddOccurrence takes an int[] and starts with result set to 0, the identity value for XOR.
• The for loop visits every element of arr exactly once and folds it into result with result ^= arr[i].
• Because x ^ x is always 0, every pair of equal values that appears an even number of times cancels out somewhere during the loop.
• The single value with an odd count never fully cancels, so it survives in result once the loop finishes.
• The main method builds a sample array, calls findOddOccurrence, and prints the result.

Step-by-Step Trace

Trace the algorithm on the input [5, 7, 2, 7, 5, 2, 5], where 5 occurs three times, 7 occurs twice, and 2 occurs twice. The expected output is 5.

At the end of each iteration, result holds the cumulative XOR of every element seen so far, so any value that has appeared an even number of times up to that point has already cancelled itself back to 0.

Examples

Example 1: A Simple Odd Count in the Middle

int[] arr1 = {2, 3, 2, 4, 4};
// 2 occurs 2 times, 3 occurs 1 time, 4 occurs 2 times
System.out.println(findOddOccurrence(arr1));
// Output: 3

Example 2: Negative Numbers

int[] arr2 = {-5, -5, -5, 9, 9};
// -5 occurs 3 times, 9 occurs 2 times
System.out.println(findOddOccurrence(arr2));
// Output: -5

Example 3: Larger Values and More Duplicates

int[] arr3 = {12, 15, 15, 12, 20, 12, 12};
// 12 occurs 4 times, 15 occurs 2 times, 20 occurs 1 time
System.out.println(findOddOccurrence(arr3));
// Output: 20

Common Mistakes to Avoid

These are the mistakes candidates actually make when solving this exact problem, not generic advice.

• Reaching for a HashMap by default – counting occurrences with a HashMap<Integer, Integer> works, but it uses O(n) extra space when the XOR trick solves the same problem in O(1) space. Recognize the even/odd-count pattern and reach for ^= instead.
• Seeding result with the wrong value – initializing result to something other than 0, such as Integer.MIN_VALUE or the first array element, corrupts every XOR that follows. Always start from 0, the identity value for XOR.
• Assuming the input guarantee always holds – if the array actually contains more than one value with an odd count, the loop silently returns the XOR of those values instead of either one, with no error raised. Validate the input or document the assumption clearly if correctness depends on it.
• Confusing XOR with a running sum – trying to solve this with sum(all) - 2 * sum(distinct pairs) is more error-prone and risks integer overflow on large values. The branch-free ^= approach avoids both problems.
• Sorting the array first “just in case” – XOR is commutative and associative, so the order of elements never affects the final result. Sorting only adds unnecessary O(n log n) time.

Additional Considerations

The algorithm runs in O(n) time because it visits each element exactly once, and it uses O(1) extra space because it only ever needs the single result variable regardless of the array size. This makes it strictly better than the HashMap-based counting approach on both dimensions.

Edge Cases to Test

Walk through these boundary inputs before calling the solution complete.

• Single-element array
• All other elements appearing exactly twice
• Negative numbers present
• Zero as the odd-occurring element
• Integer.MIN_VALUE or Integer.MAX_VALUE present
• Large array with many duplicate pairs
• More than one value with an odd count (violates the problem’s contract)
• Empty array

Integer.MIN_VALUE is worth calling out specifically because negating it or taking its absolute value overflows in Java, though the XOR approach never needs to do either, which is one more reason it is the safer choice here. An empty array has no majority odd-count element at all, so findOddOccurrence should either throw IllegalArgumentException or document that the caller must guarantee a non-empty input.

Interview Follow-up Questions

• What if exactly two elements each occur an odd number of times, and you need to find both? – XOR all elements to get the combined XOR of the two answers, then use any set bit in that result to split the array into two groups and XOR each group separately.
• What if the array arrives as a stream of unknown length instead of being held in memory? – maintain a running XOR as each value arrives; the loop body stays identical, only the termination condition changes from end-of-array to end-of-stream.
• What if every other element occurs exactly three times instead of twice, and you need the one that occurs once? – plain XOR fails here because three copies do not cancel to zero. Count set bits at each of the 32 bit positions across all elements and take bitCount % 3 per position to rebuild the answer.
• What if the input array must remain completely untouched and you are limited to a handful of local variables? – the XOR solution already satisfies this constraint since it never writes back into arr and uses only result and the loop index; explain why a HashMap-based approach would violate this restriction.

Conclusion

The XOR trick turns a problem that looks like it needs a counting structure into a single pass with one integer variable. Once you recognize the even/odd-count pattern, the same result ^= value idiom reappears across many other array problems, including finding a single missing number or the one non-repeating element among duplicates.

Try adapting the program in this guide to print which bit positions differ between the odd-occurring element and zero, or extend it to handle the two-odd-elements variant from the interview follow-up questions above. You can learn more about array-based interview problems in our Arrays category.