Day 11 : 30 Day LeetCode May Challenges

Problem_statement11.txt

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once.

 

Example 1:

Input: [1,1,2,3,3,4,4,8,8]
Output: 2
Example 2:

Input: [3,3,7,7,10,11,11]
Output: 10
 

Note: Your solution should run in O(log n) time and O(1) space.

Single_Element_in_sorted_array.cpp

class Solution {
public: 
        int singleNonDuplicate(vector<int>& nums) {
        int n = nums.size();
        if(n == 1)
            return nums.front();
        int left = 0;
        int right = n-1;
        int mid = 0;
        while (left <= right) {
            mid = left+(right-left)/2;
            if (mid%2 == 0) {
                if (nums[mid] == nums[mid-1]) {
                    right = mid-2;//we check the right side of mid because of odd number of elemnts
                }
                else if (nums[mid] == nums[mid+1]) {
                    left = mid+2;//we check the left side of mid because of odd no of elemnts to left of mid
                }
                else 
                    break;
            }
            else {
                //crucial steps
                if (nums[mid] == nums[mid-1]) {
                    left = mid+1;//we move one step ahead for odd position
                }
                else if (nums[mid] == nums[mid+1]) {
                    right = mid-1;
                }
            }
        }
        return nums[mid];
    
        /*int n = nums.size();
        int i;
        for(i=1; i<n; i+=2){
            if(nums[i] != nums[i-1])
                break;
        }
        return nums[i-1];
        */
        /*
        int ans = nums[0];
        int n = nums.size();
        for(int i=1; i<n; i++){
            ans = ans^nums[i];
        }
        return ans;
        */
        /*
        unordered_set<int> s;
        for(int x:nums){
            if(s.count(x) == 0){
                s.insert(x);
            }
            else
                s.erase(x);
        }
        auto it = s.begin();
        return *(it);
        */
    }
};