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.

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.

## 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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | /* Find the number which occur only once in an array using HashMap */ public class ElementAppearOnce { public static int singleNonDuplicateUsingMap(int[] arr) { int res = 0; //Declare a map Map<Integer, Integer> countMap = new HashMap<>(); //Traverse an array and create a key and value pair for(int i = 0 ; i < arr.length; i++) { countMap.put(arr[i], countMap.getOrDefault(arr[i], 0) + 1); } /* Traverse a map and check the number which occur only once */ for(Map.Entry<Integer, Integer> entry : countMap.entrySet()) { if(entry.getValue() == 1) { res = entry.getKey(); break; } } return res; } public static void main(String[] args) { int[] arr = {1, 1, 2, 2, 3, 3, 4, 5, 5}; int result = singleNonDuplicateUsingMap(arr); System.out.println(result); } } |

## 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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | /* Find the Element that Appears once in a Sorted Array using constant space. */ public class ElementAppearOnce { public static int singleNonDuplicateUsingXor(int[] arr) { int res = 0; for(int i: arr) { res ^= i; } return res; } public static void main(String[] args) { int[] arr = {1, 1, 2, 2, 3, 3, 4, 5, 5}; int result = singleNonDuplicateUsingXor(arr); System.out.println(result); } } |