LESSON 348 OF 348 · BIT MANIPULATION

Single Number in Scala

Practice O(n log n)

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

Constraints:

1 <= nums.length <= 3 * 10⁴
-3 * 10⁴ <= nums[i] <= 3 * 10⁴
Each element in the array appears twice except for one element which appears only once.

Note:

Your algorithm should run in O(n log n) time and use O(1) extra space.
(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:

nums = [2,1,3,1,3]
sortedNums = [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, nums[i] is the single element if both these conditions hold true:

i == 0 or nums[i - 1] != nums[i]
i == n - 1 or nums[i + 1] != nums[i]

We sort the array, thus the Time Complexity is O(n log n).
We don't use any extra arrays, so the Extra Space used is O(1).

STEP 1 OF 13

Guided

Ctrl + Enter to check