Solution Approach

We implement binary search using the standard template with first_true_index to find the single element.

The key insight is defining the feasible condition: at any index, we can check if the pair pattern has been disrupted (meaning the single element is at or before this index).

Feasible Condition: For any index mid, the condition nums[mid] != nums[mid ^ 1] indicates the pair pattern is broken. The XOR operation mid ^ 1 elegantly gives us the expected pair partner:

• If mid is even, mid ^ 1 = mid + 1 (checks next element)
• If mid is odd, mid ^ 1 = mid - 1 (checks previous element)

Binary Search Template:

Initialize:

• left = 0, right = len(nums) - 1
• first_true_index = -1 to track the first position where the pattern breaks

Loop while left <= right:

1. Calculate mid = (left + right) // 2
2. Check if feasible(mid): nums[mid] != nums[mid ^ 1]
   • If true: the single element is at mid or to its left. Store first_true_index = mid, then search left with right = mid - 1
   • If false: the pair pattern is intact, so the single element must be to the right. Search right with left = mid + 1

Return the result: After the loop, first_true_index points to the single element. Return nums[first_true_index].

The algorithm maintains the invariant that the single element is always within the search range. By finding the first index where the pair pattern breaks, we locate the single element in O(log n) time with O(1) space.

Example Walkthrough

Let's trace through the algorithm with the array [1,1,2,3,3,4,4] using the standard binary search template:

Initial state:

• Array: [1,1,2,3,3,4,4] (indices 0-6)
• left = 0, right = 6, first_true_index = -1
• Feasible condition: nums[mid] != nums[mid ^ 1] (pair pattern is broken)

Iteration 1:

• mid = (0 + 6) // 2 = 3
• Check feasible: nums[3] = 3, mid ^ 1 = 3 ^ 1 = 2, nums[2] = 2
• 3 != 2 → feasible is TRUE
• Update: first_true_index = 3, right = 2
• Search space: indices 0-2

Iteration 2:

• left = 0, right = 2
• mid = (0 + 2) // 2 = 1
• Check feasible: nums[1] = 1, mid ^ 1 = 1 ^ 1 = 0, nums[0] = 1
• 1 == 1 → feasible is FALSE
• Update: left = 2
• Search space: indices 2-2

Iteration 3:

• left = 2, right = 2
• mid = (2 + 2) // 2 = 2
• Check feasible: nums[2] = 2, mid ^ 1 = 2 ^ 1 = 3, nums[3] = 3
• 2 != 3 → feasible is TRUE
• Update: first_true_index = 2, right = 1
• Loop ends: left > right

Final state:

• first_true_index = 2
• Return nums[2] = 2

The algorithm correctly identifies 2 as the single element. The first_true_index tracks the earliest position where the pair pattern breaks, which is exactly where the single element is located.

Time and Space Complexity

The time complexity is O(log n), where n is the length of the array nums. This is because the algorithm uses binary search, which divides the search space in half with each iteration. The while loop runs at most log₂(n) times since we're repeatedly halving the search range between l and r.

The space complexity is O(1). The algorithm only uses a constant amount of extra space for the variables l, r, and mid, regardless of the input size. No additional data structures are created that scale with the input.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Wrong Binary Search Template Variant

The Pitfall: A common mistake is using while left < right with right = mid instead of the standard template with while left <= right and right = mid - 1.

Incorrect (non-standard template):

while left < right:
    mid = (left + right) // 2
    if nums[mid] != nums[mid ^ 1]:
        right = mid
    else:
        left = mid + 1
return nums[left]

Correct (standard template):

first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if nums[mid] != nums[mid ^ 1]:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1
return nums[first_true_index]

The standard template with first_true_index clearly tracks the answer and handles edge cases consistently.

2. Incorrect Pair Pattern Interpretation

The Pitfall: Misunderstanding what the XOR operation tells us about the search direction. When nums[mid] == nums[mid ^ 1], developers might incorrectly think the single element is in the left half.

The Solution: Remember: before the single element, pairs start at even indices (0, 2, 4...). After the single element, pairs start at odd indices. When we find a valid pair at mid, the pattern hasn't been disrupted yet, so we search right.

3. Edge Case with Single Element Array

The Pitfall: Not handling arrays with only one element properly.

The Solution: The standard template handles this correctly:

• When nums = [1]: left = 0, right = 0
• First iteration: mid = 0, check nums[0] != nums[1] - this would be out of bounds!

Important: For this problem, we need to handle the edge case where mid ^ 1 could be out of bounds:

# Safe version for single element
if len(nums) == 1:
    return nums[0]

Or ensure mid ^ 1 is always valid within the search range.