Single Element in a Sorted Array

PROBLEM STATEMENT

Nobita wants to impress Shizuka by guessing her lucky number.

Shizuka gave Nobita a sorted list of ‘N’ numbers such that every number occurred twice in the list except Shizuka’s lucky number which appears only once.

Nobita asked Doraemon to help him but Doraemon doesn’t have a gadget that can find Shizuka’s lucky number.

So, Doraemon called you to find Shizuka’s lucky number. The fate of Nobita lies in your hand.

Note :

1. Shizuka’s lucky number will surely be present.
2. There will only be a single lucky number.

Input Format :

The first line of input contains an integer 'T' representing the number of test cases. Then the test cases follow.

The first line of each test case contains a single integer ‘N’, representing the total number of elements present in Shizuka’s list.

The next line contains ‘N’ single-spaced elements, representing the elements of Shizuka’s list

Output Format :

For each test case, print an integer denoting the lucky number of Shizuka.

The output for each test case will be printed in a separate line.

Constraints :

1 <= T <= 5
1 <= N <= 10^5
0 <= data <= 10^9

Where ‘data’ is the value of elements of Shizuka’s list. 

Time Limit: 1 sec

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Approach 1

The idea here is to use the fact that the array is sorted and the element of the array (‘arr[i]’) is unique if it doesn't have an adjacent element that has the same value as ‘arr[i]’.

Algorithm:

If the length of the array equal to 1 then return ‘arr[0]’.
Declare a variable ‘answer’ to store Shizuka’s lucky number.
Run a loop from i = 0 to the length of the array - 1.
If ‘arr[i]’ does not have an adjacent element that is equal to ‘arr[i]’ then set ‘answer’ as ‘arr[i]’.
If the last two elements of the array are not equal then assign the last element of the array to the answer.
Finally, return the ‘answer’.

Try Problem

Approach 2

The idea here is to store the frequency of elements of the array in a hashmap. Then we will traverse all elements of hashMap and the element whose frequency is 1 will be our answer.

Algorithm:

Declare a hashMap to store the frequency of all elements of the array.
Run a loop and store the frequency of each element of the array in the hashmap.
Traverse all elements of hashMap and return the element whose frequency equal to 1.

Try Problem

Approach 3

The idea here is to use the fact that the bitwise xor of two numbers is zero. So, we will do the xor of all elements of the array, and all the numbers which occur twice get canceled out. So, in the end, we will get the number that occurs only once.

For example

Array = [1, 1, 3, 3, 5, 7, 7]

Here 1 ^ 1 ^ 3 ^ 3 ^ 5 ^ 7 ^ 7 = 5

As 1 ^ 1 = 3 ^ 3 = 7 ^ 7 = 0

Algorithm:

Declare a variable ‘answer’ and initialize it with zero.
Do xor of all elements and store the result in ‘answer’.
Finally, return the answer.

Try Problem

Approach 4

The idea here is to use binary search and move left and right using the below observation.

If mid is even, and arr[mid] == arr[mid + 1], then size of subarray [0...mid-1] (left side) is even (since the every element occurs twice), so left side does not contain the single occurrence element. Hence we need to check in [mid + 1, ..., N] subarray (right side of mid). Else we need to search for the required element on the left side.
Example:
[1, 1, 2, 2, 3(mid), 3, 5, 7, 7]
Here mid = 4. Here subarray[0…3] doesn’t contain our unique number. So we need to check in the right side of the mid i.e. subarray [5… 8].
If mid is odd, and arr[mid] == arr[mid - 1], then the size of subarray [0...mid - 2] (left side) is even (since every element occurs twice), so the left side does not contain the single occurrence element. Hence we need to check in subarray [mid + 1, ..., N] (right side of mid). Else we need to search for the required element on the left side.
Example
[1, 1, 2, 2, 3, 3(mid), 5, 7, 7]
Here mid = 5. Here subarray[0…3] doesn’t contain our unique number. So we need to check in the right side of mid i.e. subarray [6… 8].

Algorithm:

Declare three variables ‘low’, ‘high’, and ‘mid’ to use binary search and initialize ‘low’ with zero and ‘high’ with ‘n – 1’. Here ‘n’ is the length of the given array.
Run a loop until low<high.
Calculate ‘mid’ as mid = (low + high)/2
If ‘mid’ is odd and ‘arr[mid]’ equals to ‘arr[mid - 1]’ or If mid is even and ‘arr[mid]’ equals to ‘arr[mid + 1]’ then do ‘low’ = ‘mid’ + 1 i.e. move right side.
Else do high = mid i.e. move left side.
Return ‘arr[low]’.

Try Problem