Single Element in Sorted Array

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.

METHOD 1:

 

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int result = 0;
        for(int num:nums)
            result ^= num;
        return result;
    }
}

Try it on Leetcode

Here we are going to do XOR operation. Because, in the problem itself they mentioned that each number in array repeated twice and only one number occurs once. Also XOR of same number is 0 and if continue doing with all numbers the final result contains that non repeating number.

Time Complexity: O(N)

But in the question note, they mention that we have to finish the iteration in O(logN). Thus, the below solution find out result in the given time complexity.

METHOD 2:

 

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int left = 0, right = nums.length-1;
        while(left < right){
            int mid = (left + right)/2;
            if( (mid % 2 == 0 && nums[mid] == nums[mid +1]) || 
                   (mid %2 == 1 && nums[mid] == nums[mid - 1]) )
                left = mid + 1;
            else
                right = mid;
        }
        return nums[left];
    }   
}

Here, we are doing binary search.. If you check the given example, if one number present in even position then same number occur in odd position. Only non-repeated number doen't have the pair.

1) Initially left is 0, right is length-1 and we will iterate until left < right is true.

2) Find mid.

3) If any one of below conditions are true,  then increase mid by 1 and store it in left.

 a) If mid is even, then check mid+1 will be its pair.

 b) If mid is odd, then check and mid-1 will be its pair.

4) If step 3, fails, then store mid in right.

5) Repeat above steps and finally nums[left] will be a non repeating number, which will be even position.

Time Complexity: O(log N)

Related Posts:

Click here for May month challenges with solution and explanation
Click here for April month challenges with solution and explanation


Please let us know your views in comment section

Subscribe us to receive updates instantly..

Happy Coding..!!