Single Element in a Sorted Array

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

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.

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.

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

1. 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].
2. 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]’.