Find The Single Element

Approach:

We can iterate through the array and then for each element we find out if there is another element equal to the current element by iterating through the elements once again.

Algorithm:

• for ‘i’ from 0 to ‘n - 1’:
  • pass = 0
  • for ‘j’ from 0 to ‘n - 1’:
    • if(i == j)
      • continue
    • if(arr[i] == arr[j])
      • pass = 1
  • if(pass == 0)
    • return arr[i]

Approach:

We iterate through the array and store the frequency of each element in a HashMap. Then, we iterate through all the elements inside the HashMap and return the element whose frequency is 1.

Algorithm:

• Create an empty hashmap named ‘frequency’
• for ‘i’ from 0 to ‘n - 1’:
  • frequency[arr[i]]++
• for ‘i’ from 0 to ‘n - 1’:
  • if(frequency[arr[i]] == 1)
    • return arr[i]

Approach:

We iterate through the array and insert the current element if it is not equal to the top element of the stack, else we pop the topmost element from the stack. Finally, we return the only element that is present in the stack. 

This solution works, as the array is sorted and an element can occur at most two times. Therefore, whenever we encounter the second occurrence of an element, it is popped out of the stack. Since there is no second occurrence of the ‘single element’, it remains in the stack.

Algorithm:

• Create an empty stack named ‘st’
• for ‘i’ from 0 to ‘n - 1’:
  • if(!st.empty() and arr[i] == st.top())
    • st.pop()
  • else
    • st.push(arr[i])
• return st.top()

Approach:

We take advantage of the fact that the given array is sorted. We iterate through the array and if the current element is neither equal to the previous element nor the next element then we return the current element. This works because, if there were multiple occurrences of one element in the array, it would either be just before the current element or just after the current element as the array is sorted.

Algorithm:

• For ‘i’ from 0 to ‘n - 1’:
  • if((i == 0 or arr[i] != arr[i - 1]) and (i == n - 1 or arr[i] != arr[i + 1]))
    • return arr[i]

Approach:

Since we know that the XOR of an element with itself is 0 and the XOR of any number with 0 is equal to that number, we can say that the XOR of all elements of the array is equal to the single element of the array. This can be proved using the commutative and associative properties of the XOR operator.

For example: Lets say, ‘arr’ = {1, 1, 2, 3, 3}, then we have 1 ^ 1 ^ 2 ^ 3 ^ 3 = (1 ^ 1) ^ 2 ^ (3 ^ 3) = 0 ^ 2 ^ 0  = 2, where ‘^’ denotes the bitwise XOR operation.

 Hence we iterate through the elements of the array, doing the bitwise XOR of elements of the array. We return the result of XOR over the entire array.

Algorithm:

• ‘xr’ = 0
• for ‘i’ from 0 to ‘n - 1’:
  • ‘xr’ ^= ‘arr[i]’
• Return ‘xr’.

Approach:

As the array is sorted, we can make the following observations:

(i) For the elements before the ‘single element’, if ‘i’ is even, then ‘arr[i]’ is equal to ‘arr[i + 1]’, else if ‘i’ is odd, then ‘arr[i]’ is not equal to ‘arr[i + 1]’.

(ii) For the elements not before the ‘single element’, if ‘i’ is odd, then ‘arr[i]’ is equal to ‘arr[i + 1]’, else if ‘i’ is even, then ‘arr[i]’ is unequal to ‘arr[i + 1]’.

Let’s define a boolean function F(i), given by:

F(i) = {1, when (i == n - 1) or (arr[i] == arr[i + 1] and ‘i’ is even) or (arr[i] != arr[i + 1] and ‘i’ is odd) 

           0, otherwise }

We see that the function is monotonic and that it gives a value of 1 for all indices that are less than the ‘single element’ and from the ‘single element’ onwards we get a value of 0.

Hence we can use ‘binary-search’ to find the single element.

Algorithm:

• Let ‘lo’ = 0, ‘hi’ = ‘n’ - 2
• while(lo <= hi):
  • mid = (lo + hi) / 2
  • if(F(mid) == 1):
    • lo = mid + 1
  • else
    • hi = mid - 1
• return arr[lo]