Problem

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.

Your solution must run in O(log n) time and O(1) space. (link)

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

Solution

Brute force Approach

he condition to determine whether the ith index element is unique or not is as follows: nums[i-1] != nums[i] and nums[i] != nums[i+1]. Take care of edge cases for i = 0 and i = n-1.

class Solution {
    public int singleNonDuplicate(int[] nums) {

        int n = nums.length;

        if(n==1) return nums[0];


        for(int i=0; i<n; i++){
            if(i==0){
                if(nums[i]!=nums[i+1]) return nums[i];
            }
            else if(i==n-1){
                if(nums[i]!=nums[i-1]) return nums[i];
            }
            else{
                if(nums[i]!=nums[i+1] && nums[i]!=nums[i-1]) return nums[i];
            }
        }

        return -1;
    }
}

Optimal Approach - Binary Search

Given that the array is sorted, we employ binary search methodology. Upon determining the midpoint, we ascertain whether it constitutes a single element by comparing it with nums[mid-1] and nums[mid+1]. If it satisfies the condition, we return. Otherwise, we proceed to identify which half contains the single element.

Pattern:

• If the array contains no single element, each element x will initially appear at an even index, followed by its duplicate at an odd index. This pattern is represented as (x, x) => (even_index, odd_index).

• However, if a single element exists within the array, it divides the array into two sections. The original pattern still holds true, with elements appearing as (x, x) => (even_index, odd_index) before the single element. Subsequently, after the single element, the pattern reverses: the first element is found at an odd index, followed by its duplicate at an even index, depicted as (y, y) => (odd_index, even_index).

We examine the edge cases initially to prevent unnecessary checks during the binary search. Following that, we set the lower bound to 1 and the upper bound to n-2.

Regarding the algorithm, when we encounter the midpoint element where the pattern follows (even_index, odd_index), we proceed to the right half. Conversely, if the observed pattern is (odd_index, even_index), we navigate to the left half.

class Solution {
    public int singleNonDuplicate(int[] nums) {

        int n = nums.length;
        if(n==1) return nums[0];

        if(nums[0]!=nums[1]) return nums[0];
        if(nums[n-1]!=nums[n-2]) return nums[n-1];

        int low = 1;
        int high = nums.length-2;

        while(low<=high){
            int mid = (low+high)/2;

            if(nums[mid]!=nums[mid-1] && nums[mid]!=nums[mid+1]) return nums[mid];

            // (even_index, odd_index)
            if((mid%2==0 && nums[mid]==nums[mid+1]) || (mid%2==1 && nums[mid]==nums[mid-1]))
                low = mid + 1;
            else
                high = mid - 1;

        }

        return -1;
    }
}

Optimal Approach - Binary Search (xor)

This is exactly the same as the previous binary approach. The only difference is that we do not check for the single element; instead, we eliminate the half using simple XOR operations. Finally, 'low' points to the index of the single element.

If the mid index is odd, then the mid^1 index will be the previous index, which is even.

If the mid index is even, then the mid^1 index will be the next index, which is odd.

So, regardless of whether the mid index is even or odd, it checks whether our pattern falls within (even_index, odd_index) only. If yes, we eliminate the left half and move towards the right half.

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int low = 0;
        int high = nums.length-2;

        while (low<=high){
            int mid = (low+high)/2;
            if (nums[mid]==nums[mid^1])
                low = mid+1;
            else
                high = mid-1;
        }
        return nums[low];
    }
}