Odd one out! (thrice variant)

Editorials
1

[Jump to article]

Problem

You are given an array where:

  • Every element appears exactly three times
  • Except for one element that appears only once

Find that unique element in O(n) time and O(1) extra space.

Naïve Approaches

  • HashMap / Counter: track frequencies. Costs O(n) time and O(n) space.
  • Sort: then scan for the singleton. Costs O(n log n) time.

We want better: O(n) time and O(1) space.

Bitwise State Machine Trick

Each bit position behaves independently.
If a bit appears in numbers three times, it should be cleared out.
So we design a state machine with two masks:

  • ones → bits that have appeared once
  • twos → bits that have appeared twice

Transitions:

  1. Add the new number’s bits into ones/twos
  2. Whenever a bit reaches count 3, clear it from both.

Implementation

int findSingleElement(int arr[], int n) {
    int ones = 0;  // Bits seen exactly once
    int twos = 0;  // Bits seen exactly twice

    for (int i = 0; i < n; i++) {
        // Step 1: add new bits into twos if they are already in ones
        twos |= (ones & arr[i]);

        // Step 2: toggle bits in ones
        ones ^= arr[i];

        // Step 3: mask out bits that have appeared three times
        int threes = ones & twos;
        ones &= ~threes;
        twos &= ~threes;
    }

    return ones; // holds the unique element
}

Example Walkthrough

Array: [6, 2, 2, 2, 6, 6, 5]

Binary:

  • 6 = 110
  • 2 = 010
  • 5 = 101

At the end:

  • ones = 5 (101) → correct answer.

Complexity

  • Time: O(n) (single pass)
  • Space: O(1) (just two integers)

Key Idea

  • Each bit “cycles” through states:
    • 0 → ones → twos → cleared
  • The lone element’s bits never reach the third state, so they remain in ones.

Extensions

  • Works for signed integers as well (same logic).
  • Can be generalized to “every element appears k times except one” by keeping more bitmasks or by summing each bit column modulo k.
1 Like