Single Element in a Sorted Array

How it works

We can use XOR with 1 to elegantly find the pair index. For even indices, m ^ 1 gives m + 1; for odd indices, it gives m - 1. This means nums[m] should equal nums[m ^ 1] if we are in the portion before the single element. If they differ, the single element is at or before index m.

Steps

1. Initialize l = 0 and r = n - 1.
2. While l < r:
   • Compute the middle index m.
   • If nums[m] != nums[m ^ 1], the single element is at or before m; set r = m.
   • Otherwise, the single element is after m; set l = m + 1.
3. Return nums[l].

Complexity

• Time complexity: O(log n)
• Space complexity: O(1)

Things to watch for

Forgetting the Array is Sorted

Many candidates jump straight to the XOR solution without recognizing that the sorted property enables an O(log n) binary search approach. While XOR works correctly, it only achieves O(n) time complexity and fails to leverage the key constraint that makes this problem unique.

Incorrect Index Parity Logic

The binary search solution relies on understanding that before the single element, pairs start at even indices (index 0, 2, 4...) and after it, this pattern shifts. A common mistake is getting the parity check backwards or not properly handling whether to compare with the left or right neighbor based on the current index.

Off-by-One Errors in Boundary Checks

When checking neighbors at m-1 or m+1, failing to validate bounds can cause array index out-of-bounds errors. This is especially problematic at the edges of the array where the single element might be the first or last element.

from typing import List

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1

        while l < r:
            m = (l + r) >> 1
            if nums[m] != nums[m ^ 1]:
                r = m
            else:
                l = m + 1

        return nums[l]

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;

        while (l < r) {
            int m = (l + r) >> 1;
            if (nums[m] != nums[m ^ 1]) {
                r = m;
            } else {
                l = m + 1;
            }
        }

        return nums[l];
    }
};