The challenge
Return the single value that appears once when every other value appears exactly twice.
Sorted, nonempty array of odd length; exactly one singleton and all other counts are two.
Example
[1, 1, 2, 3, 3, 4, 4] → 2.
Use the walkthrough below to inspect the input and each state change.
See Pair parity, step by step
Inspect the comparison, the invariant, and the next boundary.
Inclusive candidate indices
Current comparisonResolved positionNumbers below = indices
- Left
- 0
- Middle
- —
- Right
- 6
Step 01 / 4
Start with the candidate indices
The retained interval contains the answer whenever it exists. Watch why each comparison can discard one side.
left = 0; right = 6Recorded result so far
Not resolved
View exact input
Input: [1,1,2,3,3,4,4]
Put it into code
Before the singleton, pairs start at even indices. Align mid to an even index so a pair comparison tells you which side changed parity.
Indices are zero-based. C++ uses C++17 or later.
def single_element(nums):
# Sorted, nonempty; one singleton, all others occur exactly twice.
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
mid -= mid % 2 # First index of a candidate pair.
if nums[mid] == nums[mid + 1]:
left = mid + 2
else:
right = mid
return nums[left]#include <vector>
int single_element(const std::vector<int>& nums) {
int left = 0, right = static_cast<int>(nums.size()) - 1;
while (left < right) {
int mid = left + (right - left) / 2;
mid -= mid % 2;
if (nums[mid] == nums[mid + 1]) left = mid + 2;
else right = mid;
}
return nums[left];
}