A metro gate writes down the card number of every scan. A passenger scans once to enter and once to leave, so each card appears twice. Only one card appears once, because that passenger lost the card on the way out.
The scan log nums is sorted from small to big. Return the card number that appears only once.
The solution should take O(log n) time and only O(1) extra space.
Examples
Example 1:
Input: nums = [2,2,5,5,9,10,10]
Output: 9
Explanation: Every number comes in a pair, except 9.
Example 2:
Input: nums = [4,6,6,8,8]
Output: 4
Explanation: The single number can be the first one. Here it is 4.
Example 3:
Input: nums = [1,1,3,3,7]
Output: 7
Explanation: The single number can also be the last one. Here it is 7.