Find the element that appears once in sorted array

Learn how to find the element that appears once in sorted array.

In the given array all elements appear twice except for one, we have to find that and return it.

Example

Input:
[1,1,2,3,3,4,4,8,8]
[3,3,7,7,10,11,11]

Output:
2
10

There are two variants of this problem.

1. In which all elements appear twice except for one.
2. In which there will be only 1 element with single count and other can be of any frequency.

We will solve both the variants.

Find the element that appears once in a sorted array where each element appears twice.

The naive approach is to use a hash table to count the frequency of all the elements of the array and then return the element with 1 count. This will take O(n) time and O(n) space.

Another approach is two use XOR operator to get the element with single count because num ^ num is 0.

So if we iterate through the array and compare the element with next element using XOR operator then we will get the element with with single frequency.

const elementWithSingleCount = (arr) => {
   let num = 0;
   
   for(let val of arr){
     num ^= val;
   }
  
  return num;
}

Input:
console.log(elementWithSingleCount([1,1,2,3,3,4,4,8,8]));
console.log(elementWithSingleCount([3,3,7,7,10,11,11]));

Output:
2
10

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

---

Find the element that appears once in a sorted array where other elements appear in any frequency.

Comparing with XOR operator works fine if the frequency of elements are even like 0, 2, 4, 6…

But when the frequency is odd it fails.

One way is using the naive approach of counting the frequency with hash table.

But we will use another approach here. We will be using binary search to look for the elements with single count in the array.

Implementation

• Use binary search and start looking for element in the sorted array which appears only once.
• An element has frequency one only if its next and prev elements are different, that means it has appeared once.
• So in each iteration search in both the range that is lower and upper and return element when found.

const singleNonDuplicate = (nums) => {
    let num = [];
    binarySearch(nums, 0, nums.length - 1, num);
    return num[0];
};

const binarySearch = (nums, l, h, num) => {
    if(l <= h){
        const mid = Math.ceil((l + h) / 2);
        
        //if the next and prev element are different than current that means it is a single element.
        if(nums[mid] !== nums[mid + 1] && nums[mid] !== nums[mid - 1]){
                num.push(nums[mid]);
                return;
        }

        binarySearch(nums, mid + 1, h, num);
        binarySearch(nums, l, mid - 1, num);
    }
}

Input:
console.log(singleNonDuplicate([1,1,2,2,3,3,3,4,4,4,4,8,8,10]));
console.log(singleNonDuplicate([1,1,2,2,2,3,4,4,4,4,8,8]));

Output:
10
3

Time complexity: O(n).
Space complexity: O(n) considering the call stack.