Problem Description

You have a sorted array where every integer appears exactly twice, except for one integer that appears only once. Your task is to find and return that single element.

The array is already sorted in ascending order. For example, in the array [1,1,2,3,3,4,4,8,8], the number 2 appears only once while all other numbers appear twice.

The challenge has specific performance requirements:

• Your solution must run in O(log n) time complexity, which means you cannot simply iterate through the array
• Your solution must use O(1) space complexity, meaning you can only use a constant amount of extra space

The O(log n) time requirement suggests that a binary search approach should be used rather than a linear scan through the array.

Intuition

Since we need O(log n) time complexity, we should think about binary search. But how can binary search help us find the single element?

Let's observe a pattern in arrays with all pairs except one single element. Before the single element appears, pairs start at even indices (0, 2, 4, ...). For example, in [1,1,2,2,3,4,4], the pairs (1,1) and (2,2) start at even indices 0 and 2.

However, after the single element appears, this pattern breaks. The pairs now start at odd indices. In the same example, after the single element 3 at index 4, the pair (4,4) starts at odd index 5.

This gives us a key insight: we can check any middle position and determine which half contains the single element by checking if the pair pattern is normal or disrupted.

For any index mid:

• If mid is even, its pair should be at mid + 1 in a normal pattern
• If mid is odd, its pair should be at mid - 1 in a normal pattern

We can elegantly handle both cases using XOR: mid ^ 1. This operation flips the last bit, giving us mid + 1 when mid is even, and mid - 1 when mid is odd.

Now, if nums[mid] == nums[mid ^ 1], the pattern is normal up to this point, meaning the single element must be in the right half. Otherwise, if nums[mid] != nums[mid ^ 1], the pattern is already disrupted, so the single element is in the left half (including mid itself).

By repeatedly narrowing down the search space this way, we can find the single element in O(log n) time.

Learn more about Binary Search patterns.

Solution Approach

We implement binary search with left and right pointers to find the single element.

Initialize two pointers:

• l = 0 (left boundary)
• r = len(nums) - 1 (right boundary)

The binary search continues while l < r:

1. Calculate middle position: mid = (l + r) >> 1

   • The right shift operator >> 1 is equivalent to dividing by 2

2. Check pair pattern at middle position: Compare nums[mid] with nums[mid ^ 1]

   • The XOR operation mid ^ 1 gives us:
     • mid + 1 if mid is even (flips 0 to 1 in the last bit)
     • mid - 1 if mid is odd (flips 1 to 0 in the last bit)
   • This elegantly handles both cases in one expression

3. Narrow down the search space:

   • If nums[mid] != nums[mid ^ 1]: The pair pattern is already broken at mid, meaning the single element is at mid or to its left. Set r = mid to search in [l, mid]
   • If nums[mid] == nums[mid ^ 1]: The pair pattern is normal up to mid, meaning the single element must be to the right. Set l = mid + 1 to search in [mid + 1, r]

4. Return the result: When the loop ends with l == r, we've found the position of the single element. Return nums[l]

The algorithm works because it maintains an invariant: the single element is always within the range [l, r]. By checking the pair pattern at the middle position, we can determine which half contains the single element and eliminate the other half, achieving O(log n) time complexity with O(1) space.

Example Walkthrough

Let's trace through the algorithm with the array [1,1,2,3,3,4,4]:

Initial state:

• Array: [1,1,2,3,3,4,4] (indices 0-6)
• l = 0, r = 6

Iteration 1:

• mid = (0 + 6) >> 1 = 3
• Check pair pattern: nums[3] = 3, mid ^ 1 = 3 ^ 1 = 2
• Compare nums[3] with nums[2]: 3 != 2
• Pattern is broken at mid, so single element is at mid or left
• Update: r = mid = 3
• Search space: [1,1,2,3] (indices 0-3)

Iteration 2:

• l = 0, r = 3
• mid = (0 + 3) >> 1 = 1
• Check pair pattern: nums[1] = 1, mid ^ 1 = 1 ^ 1 = 0
• Compare nums[1] with nums[0]: 1 == 1
• Pattern is normal, so single element is to the right
• Update: l = mid + 1 = 2
• Search space: [2,3] (indices 2-3)

Iteration 3:

• l = 2, r = 3
• mid = (2 + 3) >> 1 = 2
• Check pair pattern: nums[2] = 2, mid ^ 1 = 2 ^ 1 = 3
• Compare nums[2] with nums[3]: 2 != 3
• Pattern is broken at mid, so single element is at mid or left
• Update: r = mid = 2
• Search space: [2] (index 2)

Final state:

• l = 2, r = 2 (loop exits as l == r)
• Return nums[2] = 2

The algorithm correctly identifies 2 as the single element. Notice how the XOR operation elegantly handles checking the correct pair partner: when mid is even (like 2), it checks the next element; when mid is odd (like 1 or 3), it checks the previous element.

Solution Implementation

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. Incorrect Pair Pattern Interpretation

The Pitfall: A common mistake is misunderstanding what the XOR operation tells us about the search direction. When nums[mid] == nums[mid ^ 1], developers might incorrectly think:

• "The single element must be in the left half since we found a valid pair"
• Or get confused about which direction to search based on whether mid is even or odd

Why This Happens: The XOR trick mid ^ 1 can be counterintuitive. When mid is even and forms a pair with mid + 1, it means all elements up to and including this pair are correctly paired, so the single element must be after position mid + 1.

The Solution: Remember the invariant: before the single element appears, the first element of each pair will be at an even index (0, 2, 4...). After the single element, this pattern shifts, and the first element of each pair will be at an odd index. When we find a valid pair at mid, we know the pattern hasn't been disrupted yet, so we search right.

2. Off-by-One Error in Binary Search Update

The Pitfall: Using left = mid instead of left = mid + 1 when the pair is valid, or using right = mid - 1 instead of right = mid when the pair is broken. This can cause:

• Infinite loops (when left = mid and left + 1 == right)
• Missing the single element entirely

Why This Happens: Standard binary search often uses right = mid - 1 after checking the middle element. However, in this problem, when the pair is broken at mid, the single element could BE at position mid itself.

The Solution:

• When pair is valid: Use left = mid + 1 because we've confirmed both mid and mid ^ 1 are paired correctly
• When pair is broken: Use right = mid (not mid - 1) because mid itself could be the single element

3. Edge Case with Array Length

The Pitfall: Not considering arrays with only one element, or assuming the array always has an odd length. The code might crash or return incorrect results.

Why This Happens: The problem states every element appears twice except one, implying the array length must be odd. However, edge cases like nums = [1] might not be handled properly if we don't think about the boundary conditions.

The Solution: The current implementation handles this correctly because:

• When nums = [1], left = 0 and right = 0, so the while loop doesn't execute
• The function returns nums[left] which is nums[0], the correct answer
• No special case handling is needed, but it's important to verify this works