Single Element in a Sorted Array LeetCode Solution

Table of Contents

Problem Statement:

Single Element in a Sorted Array LeetCode Solution says that – 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.

Example 1:

Input:

 nums = [1,1,2,3,3,4,4,8,8]

Output:

Example 2:

Input:

 nums = [3,3,7,7,10,11,11]

Output:

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁵

ALGORITHM –

IDEA –

In order to find a single Element in a Sorted Array. First, we will use the concept of binary search and xor in this question.
Basically, we will focus on the single element in this question. So our position starts with an even index i.e zero and according to questions, every element will occur double time except a single element. We will start with the even index then odd then even and repeat…..
if our element is present at the event index that means this is the first one of the double element so if our element present at the even index then we will check for the next element by using XOR and if the next element is the same as previous that’s mean the sequence is correct from starting or we can say that there is no single element in an array till now.
The same is in the case of the odd index. odd index means the element is the second one of double if the element is at the odd index then will check for the previous one and if both match then we can say that there is no single element present till now.
We will check all the conditions using Binary search if the middle element is equal to middle^1 then low = mid+1 i.e no single element is present in the array from starting to till now.
Else high = mid. i.e single element is present in the array in the first half.

XOR VALUES –

EVEN – ODD –

0^1 = 1 1^1 = 0

2^1 = 3 3^1 = 2

4^1 = 5 5^1 = 4

6^1 = 7 7^1 = 6

At last, we will return nums[low].
Hence, we will find the Single Element in a Sorted Rotated Array.

Image –

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        low = 0
        high = len(nums)-1
        
        while(low < high):
            mid = (low+high)//2
            if nums[mid] == nums[mid^1]:
                low = mid+1
                
            else:
                high = mid
                
        return nums[low]

class Solution {
    public int singleNonDuplicate(int[] nums) {
        
        int low = 0;
        int high = nums.length-1;
        
        while(low < high){
            
            int mid = (low+high)/2;
            if(nums[mid] == nums[mid^1]){
                low = mid+1;
            }
            else{
                high = mid;
            }
            
            
        }
        return nums[low];
        
    
    }
}

Complexity Analysis for Single Element in a Sorted Array LeetCode Solution

Time Complexity : O(LOGN), As we have used Binary Search in this question.

Space Complexity : O(1), As we haven’t taken any extra space.