Table of contents

• Given problem
• Using XOR bitwise operator
• Using Binary Search algorithm
• Wrapping up

Given 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.

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

Using XOR bitwise operator

When reading the problem statement, the property of elements is that each element appears twice. To take advantage of this property, we can use XOR bitwise operator for all elements. Just because applying two same elements with XOR operator will be 0.

To understand why we have this property, we need to look at the formulation:

• 1 + 1 = 0
• 0 + 0 = 0
• 0 + 1 = 1
• 1 + 0 = 1

For example: 3 = 1100 => 1100 + 1100 = 0000

To know more about the bitwise operations, we can look at the following article Bit manipulation.

Below is our source code:

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

The complexity of this solution is:

• Time complexity: O(n).
• Space complexity: O(1).

Using Binary Search algorithm

1. Analysis

   Due to the sorted array, Binary Search can be applied in this case. We will choose the third invariant of Binary Search.

   • Our requirement is to find the element’s value that is repeated one time.

     So we need to seek the conditions that relates to mid pointer in Binary Search algorithm.

     Below are the two cases that our value is satisfied the conditions of mid pointer.

     • The mid will be at the middle of the array.

       

       In this case, the element with value 10 is compared with its adjacent elements. So our result will be:

         int left = 0;
         int right = nums.length;
       
         ...
       
         int mid = left + (right - left) / 2;
         if (nums[mid] != nums[mid - 1] && nums[mid] != nums[mid + 1]) {
             return nums[mid];
         }
       

     • But we have another edge case. How about the element with value 10 sit at the end of the array?

       

       The mid + 1 will lead to the NullPointerException. So we will have the below segment code:

         if (nums[mid] != nums[mid - 1] && mid + 1 == nums.length) {
             return nums[mid];
         }
       

       Why do we have these conditions?

       Each element will be repeated twice. The left pointer always point to the last element that satisfies this condition. When the mid points to last element of the array, it means that the remaining elements satisfied this condition.

       Therefore, the element at the mid position will be need to check.

   • Which condition will we move the right, left pointers?

     Because the characteristic of this problem is that each element will be repeated twice. So it affects to the odd/even index of each element in the array.

     • If mid points to the odd index, we only need to compare the elements at mid and mid - 1 positions.

       • Case 1:

         

       • Case 2:

         

       So we have:

         int mid = left + (right - left) / 2;
       
         if (mid %2 != 0 && nums[mid] == nums[mid - 1]) {
             left = mid;
         } else {
             right = mid;
         }
       

     • If mid points to the even index, we only need to compare the elements at mid and mid + 1 positions.

       • Case 1:

         

       • Case 2:

         

       So we have:

         int mid = left + (right - left) / 2;
       
         if (mid %2 == 0 && nums[mid] == nums[mid + 1]) {
             left = mid;
         } else {
             right = mid;
         }
       

2. Solution

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

   The complexity of this solution is:

   • Time complexity: O(logn).
   • Space complexity: O(1).

Wrapping up

Refer:

540. Single Element in a Sorted Array