You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Return the single element that appears only once.
Example 1
Input: arr = [1, 1, 2, 3, 3, 4, 4, 8, 8]
Output: 2
Explanation: Every value appears twice except 2, so 2 is the single element.
Example 2
Input: arr = [3, 3, 7, 7, 10, 11, 11]
Output: 10
Explanation: All values form pairs except 10, so 10 is the required answer.
Brute Force Approach
The simplest thought is to walk through the array in steps of two. Since duplicate values stay next to each other in a sorted array, a correct pair should look like arr[i] == arr[i + 1]. The moment that pair breaks, the current value must be the single element because its partner is missing.
Algorithm
If the array has only one element, return it because that value is automatically the answer.
Start from index
0and move through the array two positions at a time so each step checks one expected pair.If
arr[i]andarr[i + 1]are different, returnarr[i]because the pair pattern breaks there.If they are equal, continue to the next pair.
If all earlier pairs are valid, return the last element because the single value is sitting at the end.
Dry Run
Single Element in Sorted Array Brute Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Returns the element that appears only once in the sorted array. */ int singleNonDuplicate(vector<int>& arr) { // Handle the smallest possible input directly. if (arr.size() == 1) { return arr[0]; } // Check expected pairs one by one. for (int i = 0; i < (int)arr.size() - 1; i += 2) { // If the pair breaks here, this value has no partner. if (arr[i] != arr[i + 1]) { return arr[i]; } } return arr.back(); }};// Driver code startsint main() { vector<int> arr = {1, 1, 2, 3, 3, 4, 4, 8, 8}; Solution obj; cout << obj.singleNonDuplicate(arr) << endl; return 0;}Complexity Analysis
Time Complexity: O(N), N is the length of array, because in the worst case most of the array may need to be checked.
Space Complexity: O(1), because constant space is used.
Better Approach
XOR has one very useful property: a number XOR itself becomes 0. So if every paired value appears exactly twice, both copies cancel each other out.
That means after XOR-ing the whole array, only the single element remains.
Reference: Xor Basics
Algorithm
Start with a variable
xorValue = 0to store the running XOR result.Traverse the array from left to right and XOR every element with
xorValue.Paired elements cancel each other because
X ^ X = 0.After the full traversal, the remaining value inside
xorValueis the single element.Return
xorValueas it contains the final single element.
Dry Run
Single Element in Sorted Array Better Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Returns the element that appears only once in the sorted array. */ int singleNonDuplicate(vector<int>& arr) { // This stores the running XOR result. int xorValue = 0; // XOR every value so matching pairs cancel out. for (int value : arr) { xorValue ^= value; } return xorValue; }};// Driver code startsint main() { vector<int> arr = {1, 1, 2, 3, 3, 4, 4, 8, 8}; Solution obj; cout << obj.singleNonDuplicate(arr) << endl; return 0;}Complexity Analysis
Time Complexity: O(N), N is the length of array, because every element is processed once.
Space Complexity: O(1), because constant space is used.
Optimal Approach
The key observation comes from index positions. Before the single element appears, every pair starts at an even index. That means indices look like (0, 1), (2, 3), (4, 5), and so on. After the single element appears, this pairing gets shifted by one position. Then pairs start at odd indices instead.
So if the middle index belongs to a proper pair, the single element must be on the right side. If the pair pattern is broken at the middle, the single element is at mid or somewhere on the left side.
The sorted nature of the array alongside a monotonic predicate (yes/no condition) makes Binary Search the ideal approach.
Algorithm
Keep two pointers,
low = 0andhigh = N - 1, to represent the current search range.While
low < high, find the middle index,mid = low + (high-low)/2.If
midis odd, move it one step left so it points to the first index of a possible pair.Compare
arr[mid]witharr[mid + 1].If both values are equal, all pairs up to
mid + 1are placed correctly, so movelowtomid + 2.Otherwise, the single element is at
midor on the left side, so movehightomid.When the loop ends, return
arr[low], this index finally contains the single Number. This is because the loop ends when low == high and low contains the final answer.
Dry Run
Single Number in Sorted Array Optimal Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Returns the element that appears only once in the sorted array. */ int singleNonDuplicate(vector<int>& arr) { // Left boundary of the current search range. int low = 0; // Right boundary of the current search range. int high = (int)arr.size() - 1; // Keep shrinking the range until only one position remains. while (low < high) { // Calculate the middle index safely. int mid = low + (high - low) / 2; // Move to the first index of the expected pair. if (mid % 2 == 1) { mid--; } // A proper pair means the single element is further right. if (arr[mid] == arr[mid + 1]) { low = mid + 2; } else { // The broken pair means the answer is at mid or to the left. high = mid; } } return arr[low]; }};// Driver code startsint main() { vector<int> arr = {1, 1, 2, 3, 3, 4, 4, 8, 8}; Solution obj; cout << obj.singleNonDuplicate(arr) << endl; return 0;}Complexity Analysis
Time Complexity: O(log2 N), N is the length of array, because half of the search range is removed in each step.
Space Complexity: O(1), because constant space is used.
Interview follow-up Questions
Binary search works because the array follows a pattern. The task is not to search for a known value, but to search for the first place where the pair pattern breaks.
Be the first to add a comment.