Start practising

Two numbers with odd occurrences

Medium Bit Manipulation Missing / Repeated Numbers Original on GeeksforGeeks

Two numbers with odd occurrences is a medium bit manipulation problem solved with the missing / repeated numbers pattern. The best approach, optimal (xor and split by a bit), runs in O(n) time and O(1) space. Below are 2 approaches in Java, from count with a hash map up.

Problem

In an array, exactly two values occur an odd number of times and every other value occurs an even number of times. Find the two values (larger first), in O(n) time and O(1) space.

Examples

Example 1

Input
arr = [4, 2, 4, 5, 2, 3, 3, 1]
Output
[5, 1]
Why
Return the larger one first.

Example 2

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

Constraints

  • 2 <= n <= 10^6
  • Exactly two values occur an odd number of times; all others occur an even number.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Count with a hash mapO(n)O(n)
Optimal (XOR and split by a bit)O(n)O(1)

1Count with a hash map

TimeO(n)
SpaceO(n)

Count occurrences and return the two with odd counts.

  1. Count; collect values with odd counts; order larger first.
Java
class Solution {
    public int[] twoOddNum(int[] arr) {
        Map<Integer, Integer> c = new HashMap<>();
        for (int x : arr) c.merge(x, 1, Integer::sum);
        int[] out = new int[2];
        int k = 0;
        for (Map.Entry<Integer, Integer> e : c.entrySet()) if (e.getValue() % 2 == 1) out[k++] = e.getKey();
        if (out[0] < out[1]) { int t = out[0]; out[0] = out[1]; out[1] = t; }
        return out;
    }
}

2Optimal (XOR and split by a bit)

TimeO(n)
SpaceO(1)

x = a ^ b. Take its lowest set bit with x & -x; a and b differ at that bit. XOR each group (bit set / bit clear) separately: pairs still cancel, leaving a in one group and b in the other.

  1. x = XOR of all; mask = x & -x.
  2. a = XOR of values with (v & mask) != 0; b = x ^ a.
  3. Return [max, min].
Java
class Solution {
    public int[] twoOddNum(int[] arr) {
        int x = 0;
        for (int v : arr) x ^= v;
        int mask = x & -x, a = 0;
        for (int v : arr) if ((v & mask) != 0) a ^= v;
        int b = x ^ a;
        return new int[] { Math.max(a, b), Math.min(a, b) };
    }
}

Edge cases to test

  • One of the two appears three times

Hints

Hint 1

XOR of everything = a ^ b, which is non-zero. Any set bit of it splits the numbers into two groups, one containing a and the other b.

FAQ

What is the best time complexity for Two numbers with odd occurrences?

Optimal (XOR and split by a bit) runs in O(n) time and O(1) extra space.

Which pattern does Two numbers with odd occurrences use?

It is a bit manipulation problem that uses the missing / repeated numbers pattern. Other problems with the same pattern: Single Number, Missing Number.

Is there a brute force solution for Two numbers with odd occurrences?

Yes. Count with a hash map takes O(n) time and O(n) space. Count occurrences and return the two with odd counts.

Which edge cases should I test for Two numbers with odd occurrences?

One of the two appears three times.