⚡ Array 14 min read

Single Element in a Sorted Array in C++

by

Single Element in a Sorted Array in C++ (LeetCode 540: Single Element in a Sorted Array) is one of the most intellectually rewarding binary search and bit-manipulation problems frequently featured in top-tier technical interviews at Meta, Google, Amazon, Apple, Microsoft, and Bloomberg. You are given a sorted array consisting of integers where every single element appears exactly twice, with the exception of one unique element that appears exactly once. The mandate is to find and return this single unique element in strict O(log N) time complexity and O(1) auxiliary space. While an unsorted array can be solved in linear time via bitwise XOR reduction, the sorted property encodes a strict index parity invariant that allows binary search to eliminate half the search space at each iteration. In this comprehensive masterclass, we will deconstruct the problem from first principles: covering the O(N) Bitwise XOR Accumulator, Linear Step-by-2 Adjacent Inspection, and the Optimal Even-Odd Binary Search using the mid ^ 1 bitwise partner trick. We will also explore hardware level bitwise execution, extensions to Single Number II and III, benchmark on 10,000,000 elements, and provide interactive “Try it yourself” challenges after every section.

🔹 Problem Topology & The Even-Odd Parity Invariant

Let us analyze a concrete sorted array with N = 9 elements: nums = [1, 1, 2, 3, 3, 4, 4, 8, 8]. The unique element is 2 located at index 2.

Index:       0    1    2    3    4    5    6    7    8
Array:      [1,   1,   2,   3,   3,   4,   4,   8,   8]
Parity:     (E)  (O)  (E)  (O)  (E)  (O)  (E)  (O)  (E)
Pairing:    [  P1  ]   U   [  P2  ]  [  P3  ]  [  P4  ]
                      ^
                      Single Element (Index 2)

Notice the structural phase shift caused by the unique element:

  • Left of the Single Element (Normal Parity Region):
    • Every duplicate pair starts at an EVEN index and ends at an ODD index (i.e., index % 2 == 0 → nums[i] == nums[i + 1]).
    • Example: Pair (1, 1) occupies indices 0 (Even) and 1 (Odd).
  • The Single Element (The Phase Shift Catalyst):
    • The single unique element resides at an EVEN index. It disrupts the alternating even-odd sequence by occupying a solitary slot.
  • Right of the Single Element (Disrupted Parity Region):
    • Every duplicate pair after the single element starts at an ODD index and ends at an EVEN index (i.e., index % 2 == 1 → nums[i] == nums[i + 1]).
    • Example: Pair (3, 3) occupies indices 3 (Odd) and 4 (Even); Pair (4, 4) occupies 5 (Odd) and 6 (Even).

The Bitwise XOR Partner Invariant (mid ^ 1)

The mathematical operation mid ^ 1 elegantly maps any index to its expected pair partner without conditional branching:

If mid is EVEN (e.g., 0, 2, 4, 6):
  0 ^ 1 = 1  (mid + 1)
  2 ^ 1 = 3  (mid + 1)
  4 ^ 1 = 5  (mid + 1)

If mid is ODD (e.g., 1, 3, 5, 7):
  1 ^ 1 = 0  (mid - 1)
  3 ^ 1 = 2  (mid - 1)
  5 ^ 1 = 4  (mid - 1)

Universal Rule: If nums[mid] == nums[mid ^ 1], the midpoint mid is on the Left (Normal Parity) side of the unique element. Therefore, the single element must be strictly to the right (→ low = mid + 1). Otherwise, it is at mid or to its left (→ high = mid).

Try it yourself

  • Given nums = [3, 3, 7, 7, 10, 11, 11], compute mid ^ 1 for mid = 4. Does nums[4] == nums[4 ^ 1] hold?
  • Why is the array length N always guaranteed to be an odd number (2k + 1)?

🔹 Approach 1: Brute Force (Bitwise XOR Accumulator: O(N))

Intuition & Reasoning: By the algebraic properties of the bitwise XOR operator (^):

1. x ^ x = 0        (Self-inverse: identical numbers cancel out)
2. x ^ 0 = x        (Identity element)
3. a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b  (Commutative and associative)

Iterating through every element and accumulating the XOR sum cancels all paired elements, directly isolating the single non-duplicate element in O(N) time without requiring the array to be sorted.

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

// Approach 1: Bitwise XOR Accumulator
// Time Complexity: O(N), Space Complexity: O(1)
int single_non_duplicate_xor(const vector<int>& nums) {
    int unique_elem = 0;
    for (int num : nums) {
        unique_elem ^= num;
    }
    return unique_elem;
}

int main() {
    vector<int> a1 = {1, 1, 2, 3, 3, 4, 4, 8, 8};
    vector<int> a2 = {3, 3, 7, 7, 10, 11, 11};
    vector<int> a3 = {5};

    cout << "--- Approach 1: Bitwise XOR Accumulator ---\n";
    cout << "Array [1, 1, 2, 3, 3, 4, 4, 8, 8] → Single Element: " << single_non_duplicate_xor(a1) << "\n";
    cout << "Array [3, 3, 7, 7, 10, 11, 11]    → Single Element: " << single_non_duplicate_xor(a2) << "\n";
    cout << "Array [5]                         → Single Element: " << single_non_duplicate_xor(a3) << "\n";

    assert(single_non_duplicate_xor(a1) == 2);
    assert(single_non_duplicate_xor(a2) == 10);
    assert(single_non_duplicate_xor(a3) == 5);
    cout << "All assertions passed successfully!\n";
    return 0;
}

Output

--- Approach 1: Bitwise XOR Accumulator ---
Array [1, 1, 2, 3, 3, 4, 4, 8, 8] → Single Element: 2
Array [3, 3, 7, 7, 10, 11, 11]    → Single Element: 10
Array [5]                         → Single Element: 5
All assertions passed successfully!

Step by Step State Trace

Tracing single_non_duplicate_xor on [1, 1, 2, 3, 3, 4, 4, 8, 8]:

Initial: unique_elem = 0
Step 1: unique_elem ^= 1 → 1
Step 2: unique_elem ^= 1 → 0 (1 cancelled)
Step 3: unique_elem ^= 2 → 2
Step 4: unique_elem ^= 3 → 1
Step 5: unique_elem ^= 3 → 2 (3 cancelled)
Step 6: unique_elem ^= 4 → 6
Step 7: unique_elem ^= 4 → 2 (4 cancelled)
Step 8: unique_elem ^= 8 → 10
Step 9: unique_elem ^= 8 → 2 (8 cancelled)
Result: 2

Complexity Analysis

  • Time Complexity (TC): O(N): Processes every element exactly once in a single sequential pass.
  • Space Complexity (SC): O(1): Uses a single 32-bit integer register.
  • Bottleneck: While universal (works on unsorted arrays), it fails to leverage the sorted property, performing N operations instead of the required O(log N).

Try it yourself

  • Why does this XOR approach work even if the array is randomly shuffled?
  • Can this XOR approach detect a single element if other elements appear 3 times? (Hint: No, 3 copies don’t cancel to 0).

🔹 Approach 2: Linear Step-by-2 Pair Inspection (O(N))

Intuition & Reasoning: Since the array is sorted, every valid pair must consist of two identical adjacent elements at (i, i + 1) starting at even indices i = 0, 2, 4, .... We can iterate with a step size of 2 (i += 2). The first even index i where nums[i] != nums[i + 1] reveals that nums[i] is the unique single element. If the loop completes without finding a mismatch, the single element is at the very last index nums[N - 1].

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

// Approach 2: Linear Stepping by 2s
// Time Complexity: O(N), Space Complexity: O(1)
int single_non_duplicate_linear_step(const vector<int>& nums) {
    const size_t n = nums.size();
    
    // Step across even indices: 0, 2, 4, ...
    for (size_t i = 0; i + 1 < n; i += 2) {
        if (nums[i] != nums[i + 1]) {
            return nums[i]; // Mismatch found at even index!
        }
    }
    
    // If all pairs matched, the unique element is at the last index
    return nums.back();
}

int main() {
    vector<int> a1 = {1, 1, 2, 3, 3, 4, 4, 8, 8};
    vector<int> a2 = {3, 3, 7, 7, 10, 11, 11};
    vector<int> a3 = {1, 1, 2, 2, 3};

    cout << "--- Approach 2: Linear Stepping by 2s ---\n";
    cout << "Array [1, 1, 2, 3, 3, 4, 4, 8, 8] → Single Element: " << single_non_duplicate_linear_step(a1) << "\n";
    cout << "Array [3, 3, 7, 7, 10, 11, 11]    → Single Element: " << single_non_duplicate_linear_step(a2) << "\n";
    cout << "Array [1, 1, 2, 2, 3]             → Single Element: " << single_non_duplicate_linear_step(a3) << "\n";

    assert(single_non_duplicate_linear_step(a1) == 2);
    assert(single_non_duplicate_linear_step(a2) == 10);
    assert(single_non_duplicate_linear_step(a3) == 3);
    cout << "All assertions passed successfully!\n";
    return 0;
}

Output

--- Approach 2: Linear Stepping by 2s ---
Array [1, 1, 2, 3, 3, 4, 4, 8, 8] → Single Element: 2
Array [3, 3, 7, 7, 10, 11, 11]    → Single Element: 10
Array [1, 1, 2, 2, 3]             → Single Element: 3
All assertions passed successfully!

Complexity Analysis

  • Time Complexity (TC): O(N): In the worst case, checks N / 2 pairs before identifying the element at the end of the array.
  • Space Complexity (SC): O(1): Requires only a single scalar index variable.
  • Inefficiencies: Performs linear sequential iteration instead of halving the search space exponentially.

Try it yourself

  • What edge case is handled by return nums.back()?
  • How many iterations does this approach perform when the single element is at index 0?

🔹 Approach 3: Optimal Binary Search with mid ^ 1 Bitwise Partner Invariant (O(log N))

Intuition & Mathematical Invariant: We maintain a binary search range [low, high] initialized to [0, N - 1]. At each iteration, we compute mid = low + (high - low) / 2 and check its partner index using mid ^ 1:

Condition: nums[mid] == nums[mid ^ 1]

If TRUE:
  The pair containing nums[mid] is correctly aligned in (Even, Odd) fashion.
  This proves the single element CANNOT be in the range [0..mid].
  It must lie strictly to the right!
  → low = mid + 1;

If FALSE:
  The pair alignment is already broken at or before mid.
  The single element must reside at mid or in the left sub-array [low..mid].
  → high = mid;

When low == high, the search window has collapsed to a single index, which is guaranteed to be the unique single element!

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

// Approach 3: Optimal Binary Search using Bitwise XOR Partner Invariant
// Time Complexity: O(log N), Space Complexity: O(1)
int single_non_duplicate_optimal(const vector<int>& nums) {
    int low = 0;
    int high = static_cast<int>(nums.size()) - 1;

    // Invariant: The single element always resides within [low, high]
    while (low < high) {
        int mid = low + (high - low) / 2;

        // mid ^ 1 checks (mid + 1) if mid is even, and (mid - 1) if mid is odd
        if (nums[mid] == nums[mid ^ 1]) {
            // Left portion is intact → unique element is to the right
            low = mid + 1;
        } else {
            // Disruption detected → unique element is at mid or to the left
            high = mid;
        }
    }

    // When low == high, both pointers have converged on the single element
    return nums[low];
}

int main() {
    vector<int> a1 = {1, 1, 2, 3, 3, 4, 4, 8, 8};
    vector<int> a2 = {3, 3, 7, 7, 10, 11, 11};
    vector<int> a3 = {1, 1, 2, 2, 3};
    vector<int> a4 = {7};

    cout << "--- Approach 3: Optimal Binary Search (mid ^ 1) ---\n";
    cout << "Array [1, 1, 2, 3, 3, 4, 4, 8, 8] → Single Element: " << single_non_duplicate_optimal(a1) << "\n";
    cout << "Array [3, 3, 7, 7, 10, 11, 11]    → Single Element: " << single_non_duplicate_optimal(a2) << "\n";
    cout << "Array [1, 1, 2, 2, 3]             → Single Element: " << single_non_duplicate_optimal(a3) << "\n";
    cout << "Array [7]                         → Single Element: " << single_non_duplicate_optimal(a4) << "\n";

    assert(single_non_duplicate_optimal(a1) == 2);
    assert(single_non_duplicate_optimal(a2) == 10);
    assert(single_non_duplicate_optimal(a3) == 3);
    assert(single_non_duplicate_optimal(a4) == 7);
    cout << "All assertions passed successfully!\n";
    return 0;
}

Output

--- Approach 3: Optimal Binary Search (mid ^ 1) ---
Array [1, 1, 2, 3, 3, 4, 4, 8, 8] → Single Element: 2
Array [3, 3, 7, 7, 10, 11, 11]    → Single Element: 10
Array [1, 1, 2, 2, 3]             → Single Element: 3
Array [7]                         → Single Element: 7
All assertions passed successfully!

Step by Step State Transition Trace

Tracing single_non_duplicate_optimal on nums = [1, 1, 2, 3, 3, 4, 4, 8, 8] (length N = 9):

Iter 1: low = 0, high = 8
        mid = 0 + (8 - 0) / 2 = 4 (Even)
        Partner: mid ^ 1 = 4 ^ 1 = 5 (Odd)
        nums[4] = 3, nums[5] = 4
        Condition: nums[4] == nums[5] (3 == 4) is FALSE!
        Action: high = mid = 4. Window shrinks to [0..4].

Iter 2: low = 0, high = 4
        mid = 0 + (4 - 0) / 2 = 2 (Even)
        Partner: mid ^ 1 = 2 ^ 1 = 3 (Odd)
        nums[2] = 2, nums[3] = 3
        Condition: nums[2] == nums[3] (2 == 3) is FALSE!
        Action: high = mid = 2. Window shrinks to [0..2].

Iter 3: low = 0, high = 2
        mid = 0 + (2 - 0) / 2 = 1 (Odd)
        Partner: mid ^ 1 = 1 ^ 1 = 0 (Even)
        nums[1] = 1, nums[0] = 1
        Condition: nums[1] == nums[0] (1 == 1) is TRUE!
        Action: low = mid + 1 = 2. Window shrinks to [2..2].

Termination: low == high (2 == 2).
Result: nums[2] = 2! Converged in exactly 3 iterations!

Complexity Analysis & Rigorous Proof

  • Time Complexity (TC): O(log N): Every iteration cuts the active search window strictly in half: T(N) = T(N / 2) + O(1) → O(log N). For N = 10,000,000, it executes at most 24 loop cycles.
  • Space Complexity (SC): O(1): Uses two integer pointers (low and high) residing in CPU registers.
  • Boundary Safety: Because high = N - 1 and mid = low + (high - low) / 2, mid is strictly less than high. When mid is even, mid ^ 1 = mid + 1 ≤ high, guaranteeing that nums[mid ^ 1] never triggers an out-of-bounds access.

Try it yourself

  • Trace the algorithm on nums = [1, 2, 2]. How many iterations does it take to return 1?
  • Why does the loop terminate when low == high instead of using low ≤ high?

🔹 Advanced Systems Topic: Hardware Bitwise Instructions & Extensions

Modern x86-64 and ARM64 microarchitectures execute bitwise XOR (XOR reg, 1) in a single CPU cycle with zero latency pipeline penalties. By substituting cumbersome conditional branches (if (mid % 2 == 0) ... else ...) with mid ^ 1, modern compilers (GCC/Clang with -O3) generate branchless assembly that completely bypasses branch prediction misses.

Extensions to General Single Number Problems

  • Single Number II (LeetCode 137): Every element appears 3 times except one that appears once. We sum bits modulo 3 across 32 bit positions or use digital logic state machines (ones and twos bitmasks) in O(N) time.
  • Single Number III (LeetCode 260): Two elements appear once, and all others appear twice. We compute the total XOR sum XOR = a ^ b, isolate the lowest set bit (diff = XOR & (-XOR)), and partition the array into two buckets to isolate a and b independently.

🔹 Lab: High Performance Benchmark Across 10,000,000 Elements

The following benchmark executable pits all three approaches against each other on an array of 10,000,000 integers across 1,000,000 repeated queries using std::chrono::high_resolution_clock:

#include <iostream>
#include <vector>
#include <chrono>

using namespace std;
using namespace std::chrono;

int single_xor(const vector<int>& nums) {
    int res = 0;
    for (int x : nums) res ^= x;
    return res;
}

int single_opt(const vector<int>& nums) {
    int low = 0, high = static_cast<int>(nums.size()) - 1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] == nums[mid ^ 1]) low = mid + 1;
        else high = mid;
    }
    return nums[low];
}

int main() {
    const size_t N = 10'000'001; // Must be odd
    const size_t TARGET_IDX = 6'543'210; // Unique element position
    cout << "Generating sorted array of " << N << " integers...\n";

    vector<int> data;
    data.reserve(N);
    int val = 1;
    for (size_t i = 0; i < N; ) {
        if (i == TARGET_IDX) {
            data.push_back(val++);
            ++i;
        } else {
            data.push_back(val);
            data.push_back(val);
            val++;
            i += 2;
        }
    }

    // Benchmark 1: Single Pass Linear XOR
    auto t0 = high_resolution_clock::now();
    int r1 = single_xor(data);
    auto t1 = high_resolution_clock::now();
    auto ms_xor = duration_cast<milliseconds>(t1 - t0).count();
    cout << "Linear XOR (1 pass over 10M elements):      " << ms_xor << " ms (Result: " << r1 << ")\n";

    // Benchmark 2: 1,000,000 Queries of Optimal Binary Search
    volatile int sink = 0;
    auto t2 = high_resolution_clock::now();
    for (int q = 0; q < 1'000'000; ++q) {
        sink += single_opt(data);
    }
    auto t3 = high_resolution_clock::now();
    auto ms_opt = duration_cast<milliseconds>(t3 - t2).count();
    cout << "Optimal BS (1,000,000 queries on 10M):      " << ms_opt << " ms (Avg per query: "
         << (ms_opt * 1000.0 / 1'000'000.0) << " µs)\n";

    return 0;
}

Benchmark Results

Generating sorted array of 10000001 integers...
Linear XOR (1 pass over 10M elements):      11 ms (Result: 3271606)
Optimal BS (1,000,000 queries on 10M):      16 ms (Avg per query: 0.016 µs)

🔹 Comparison Matrix of All Approaches

┌─────────────────────────────────────┬──────────────────┬──────────────────┬─────────────────────────────┬───────────────────────────┐
│ Approach                            │ Time Complexity  │ Space Complexity │ Invariant Check             │ Input Constraints         │
├─────────────────────────────────────┼──────────────────┼──────────────────┼─────────────────────────────┼───────────────────────────┤
│ 1. Bitwise XOR Accumulator          │ O(N)             │ O(1)             │ Bitwise cancellation        │ Any array (sorted/unsorted│
│ 2. Linear Stepping by 2s            │ O(N)             │ O(1)             │ nums[i] != nums[i+1]        │ Sorted arrays only        │
│ 3. Optimal Binary Search (mid ^ 1)  │ O(log N)         │ O(1)             │ nums[mid] == nums[mid ^ 1]  │ Sorted arrays (Optimal)   │
└─────────────────────────────────────┴──────────────────┴──────────────────┴─────────────────────────────┴───────────────────────────┘

🔹 Frequently Asked Questions (FAQs)

Q1: Why does mid ^ 1 correctly flip between even and odd indices?
In binary representation, even numbers end in 0 (e.g. 2 = 0b0010) and odd numbers end in 1 (e.g. 3 = 0b0011). XORing with 1 flips the least significant bit (LSB). Thus, 2 ^ 1 = 3 (adds 1 to an even number) and 3 ^ 1 = 2 (subtracts 1 from an odd number). This allows uniform partner lookup in a single branchless CPU instruction.

Q2: Why does the array size always have to be an odd number?
If every duplicate element appears exactly twice (generating 2k elements) and there is exactly one single element, the total array length is 2k + 1, which is mathematically guaranteed to be odd.

Q3: What if the single element is at index 0 or index N – 1?
The algorithm handles these boundary cases automatically without special branch checks. If the single element is at index 0, nums[0] != nums[1] causes high to shrink immediately to 0. If it is at index N – 1, all preceding pairs match, causing low to advance all the way to N – 1.

Q4: Why does the while loop use low < high instead of low ≤ high?
Because high = mid (rather than mid - 1), using low ≤ high would trigger an infinite loop when low == high. With low < high, the search terminates precisely when the window shrinks to a single element at low == high.

Q5: Can we solve this problem if the array is unsorted in O(log N)?
No. In an unsorted array, the information theoretic lower bound requires examining every element at least once, giving a lower bound of Ω(N). Sorting first takes O(N log N), which is slower than a direct O(N) XOR pass.

Q6: How does the bitwise XOR trick prevent out-of-bounds memory errors?
Because high = N - 1 and mid = low + (high - low) / 2, mid is strictly strictly less than high whenever low < high. When mid is even, mid ^ 1 = mid + 1 ≤ high < N, ensuring the partner index is always within valid vector memory bounds.

Q7: How does compiler optimization affect the mid ^ 1 code?
At -O2 or -O3 optimization levels, modern C++ compilers emit a single xor eax, 1 instruction and use conditional move instructions (cmov) to avoid CPU pipeline flushes caused by branch mispredictions.

Q8: What if elements can appear 3 or 4 times?
If elements appear 3 times, parity partitioning breaks. You must either use 32-bit bit counting modulo 3 (LeetCode 137) or generalize the step size to 3 in a modified ternary search.

🔹 Wrapping Up

Mastering Single Element in a Sorted Array in C++ is a milestone in understanding how structural invariants empower binary search to solve non-traditional search problems. By leveraging index parity and the bitwise partner trick (mid ^ 1), we achieve an optimal O(log N) time and O(1) auxiliary space solution. Continue expanding your binary search capabilities with our tutorials on Find Minimum in Rotated Sorted Array, Times Array Has Been Rotated, and Find Peak Element.

Leave a Comment