Start learning free

LESSON 592 OF 677 · BIT MANIPULATION

Single Number

Practice O(n log n)

You get an array of integers nums. Every value in it appears exactly twice, except one. Return the value that appears only once.


Example 1:

Input: nums = [5,3,9,3,5]
Output: 9
Explanation: 5 and 3 appear twice.
9 appears only once.

Example 2:

Input: nums = [-4,6,6]
Output: -4
Explanation: The value that appears once can be negative.

Example 3:

Input: nums = [12]
Output: 12

Constraints:

  • 1 to 30,000 numbers.
  • Each number is from -30,000 to 30,000.
  • Exactly one value appears once.
  • Every other value appears exactly twice.
Note:

Your algorithm should run in O(n log n) time and use O(1) extra space (when the array is sorted in place).
(There are faster solutions which we will discuss in future lessons)


Hints:

Let's sort the array in non-decreasing order. In this way all the equal elements will come one after another.
Let's take an example: if nums is [2,1,3,1,3], sorting it gives [1,1,2,3,3].
The single element is 2. What property does it satisfy that the other elements don't?

After sorting the array, the single element is the only one that is different than both its neighbors.
More exactly, in sorted nums, the element at index i is the single element if both these conditions hold true:
  • i is the first index, or the previous element is different from the element at index i
  • i is the last index, or the next element is different from the element at index i


We sort the array, thus the Time Complexity is O(n log n).
If we sort nums in place, we don't use any extra arrays, so the Extra Space used is O(1). (Sorting a copy, as Swift's sorted() does, would take O(n) extra space.)

STEP 1 OF 13
    Ctrl + Enter to check