
Problem Statement
In this scenario, you are provided with a sorted integer array where every number except one occurs exactly twice. Your challenge is to identify the number that appears only once. The solution should be efficient, adhering to time complexity of (O(\log n)) and space complexity of (O(1)). This indicates that the approach should utilize methodologies similar to binary search to ensure that you're able to find the unique element within a logarithmic time frame while using constant space.
Examples
Example 1
Input:
nums = [1,1,2,3,3,4,4,8,8]
Output:
2
Example 2
Input:
nums = [3,3,7,7,10,11,11]
Output:
10
Constraints
1 <= nums.length <= 105
0 <= nums[i] <= 105
Approach and Intuition
Given that the array is sorted and most numbers are in pairs (except the single element we're looking for), binary search becomes a viable option to efficiently locate the unique element. Here's a breakdown of the approach and underlying intuition based on the provided examples and constraints:
**Binary Search Foundation*: Utilize the binary search approach, but instead of searching for a specific key in a traditional sense, adjust the mid calculation to check the pairing of numbers.
Check Pairs Logic: In a normal scenario where all elements exist exactly twice:
- Numbers pair up across the mid-point uniformly if the single element hasn't appeared yet. For example, if the single element is after mid, pairs before mid are complete and correctly paired.
- If a single element shifted the order before the mid-point, then we'll notice a misalignment in pairs starting exactly from the single element's index.
Adjusting Mid-Point:
- If the middle element is the same as the one immediately next to it, and their position forms an even index, the single element must be further to the right side, so adjust the search to the right half.
- If they form an odd index, adjust the search to the left half as the single element's effect has already started.
Using these insights, the algorithm continually narrows down the search radius to locate the single element. Each step approximately divides the search scope in half, hence achieving the (O(\log n)) time complexity, while the iterative checks and adjustments ensure we are within constant space usage, satisfying the (O(1)) space constraint.
Solutions
- C++
class Solution {
public:
int findSingleElement(vector<int>& arr) {
int start = 0;
int end = arr.size() - 1;
while (start < end) {
int middle = start + (end - start) / 2;
if (middle % 2 == 1) middle--;
if (arr[middle] == arr[middle + 1]) {
start = middle + 2;
} else {
end = middle;
}
}
return arr[start];
}
};
The provided C++ code aims to solve the problem of finding a single element in a sorted array where every other element appears twice. The solution employs a binary search algorithm to efficiently locate the non-repeating element. Follow the detailed breakdown of the code:
- Initialize two pointers,
start
set to0
andend
set to the last index of the array. - Use a while loop to iterate until
start
is less thanend
. - Calculate the middle index using
start
andend
to potentially halve the search space in each iteration. - Since the elements are in pairs, adjust the
middle
index to be even, ensuring it starts at the beginning of a pair. - Compare the element at the
middle
index with the next element:- If they are equal, it means the single element is beyond this point. Thus, move the
start
pointer tomiddle + 2
. - If they are not equal, update the
end
pointer tomiddle
.
- If they are equal, it means the single element is beyond this point. Thus, move the
- After exiting the loop, the
start
pointer will point to the single element in the array.
The binary search approach ensures the algorithm runs in O(log n) time, making it very efficient for large arrays. The condition inside the while loop ensures that the search space is correctly narrowed down to the segment of the array containing the single element.
- Java
class Solution {
public int findUnique(int[] elements) {
int low = 0;
int high = elements.length - 1;
while (low < high) {
int middle = low + (high - low) / 2;
if (middle % 2 == 1) middle--;
if (elements[middle] == elements[middle + 1]) {
low = middle + 2;
} else {
high = middle;
}
}
return elements[low];
}
}
The provided Java solution is designed to identify a single element in a sorted array where every other element appears exactly twice. This algorithm is efficient, operating in logarithmic time complexity, O(log n), which is optimal for this type of search problem due to the use of a binary search pattern. Follow these steps to understand how the solution works:
- Initialize two pointers,
low
at the beginning of the array andhigh
at the end (elements.length - 1
). - Enter a loop that continues as long as
low
is less thanhigh
. This loop ensures that as soon aslow
equalshigh
, the single element has been found. - Calculate the
middle
of the current sub-array. This involves finding the average oflow
andhigh
and adjusting it if it is an odd number (if (middle % 2 == 1) middle--;
). This adjustment keeps the middle pointing to the start of a pair in the array. - Check if the element at the
middle
index is the same as the one next to it (elements[middle + 1]
). If they are the same, it indicates that the single element is further in the array, so adjustlow
to skip to the next pair (middle + 2
). If they are not the same, adjusthigh
to focus on the current pair. - When the loop exits, return the element at the
low
index, which will be your single unpaired element.
This approach guarantees that the search space is halved in each iteration, making the algorithm significantly faster than a linear scan, especially for large arrays. Ensure the array is sorted and adheres to the stated conditions (all elements, except one, appear exactly twice) for the solution to work correctly.
No comments yet.