Find the Element that Appears once in a Sorted Array

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

Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.

For example:

Example 1:

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

Except 2 every other element appears twice.

Example 2:

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

Except 10 every other element appears twice.

find the element that appears once in a sorted array

find the element that appears once in a sorted array

In this tutorial, I am going to discuss multiple approaches and their time complexities to solve this problem. I have also added the link of video tutorial at the end of this post.

Subscribe Our Tutorials

Get Latest Updates on Facebook

Programming video tutorials

Find the Element that Appears once in a Sorted Array using HashMap

The idea here is to create a map of number and it’s count. Once we know the count of each number of an array we can easily find the number which occur only once in an array.

The time complexity of this approach is O(n) and the space complexity is also O(n).

Find first non-repeating character in a string

Find the Element that Appears once in a Sorted Array using XOR

In this example, we are using the property of XOR.

* XOR (Exclusive or) of a number with itself is zero.

For example:

1 ^ 1 = 0
2 ^ 2 =0

* XOR of a number with zero is number itself.

For example:

3 ^ 0 = 3
2 ^ 0 = 2

The idea here the number which appears twice is cancelled out when we do the XOR. So, we get the number which occur only once.

The time complexity of this approach is O(n). This method take constant space.

If you have any doubt regarding this method. You can watch the video tutorial which is present at the end of this post in which i have explained this method step by step.

Find next greater element in an array

About WebRewrite

I am technology lover who loves to keep updated with latest technology. My interest field is Web Development.
Tagged , , . Bookmark the permalink.