Start learning free

LESSON 400 OF 442 · BIT MANIPULATION

Single Number in Scala: O(n) Time, O(1) Space with XOR

Practice O(n) Read the full explanation

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 * 104
  • -3 * 104 <= nums[i] <= 3 * 104
  • Each element in the array appears twice except for one element which appears only once.
Note:

Your algorithm should run in O(n) time and use O(1) extra space.


Hints:

What property can help identify a number that appears only once when all others appear twice?
Think about a bitwise operation that cancels out equal values.

XOR (^) has two key properties:
  • x ^ x = 0 — equal numbers cancel each other out
  • x ^ 0 = x — XOR with 0 leaves the number unchanged
If you XOR all elements in the array together, every duplicate pair cancels out to 0, leaving only the single number.
For example: 4 ^ 1 ^ 2 ^ 1 ^ 2 = 4

We iterate through the array once, so the Time Complexity is O(n).
We use only one extra variable, so the Extra Space is O(1).
STEP 1 OF 4
    Ctrl + Enter to check

    SCALA · BIT MANIPULATION

    Single Number in Scala, explained

    Problem overview

    The method singleNumber(nums: Array[Int]): Int receives a non-empty array in which every value appears exactly twice, except for one value that appears once. It must return that single value.

    For nums = [2, 2, 1] the answer is 1. For nums = [4, 1, 2, 1, 2] it is 4. For nums = [1] it is 1. The array has up to 30,000 elements, each between -30,000 and 30,000.

    The lesson asks for O(n) time and O(1) extra space. A hash map of counts, or a sorted copy, would be O(n) space or O(n log n) time. A bitwise operation does it with one variable.

    Approach: equal numbers cancel under XOR

    The XOR operator, written ^ in Scala, compares two integers bit by bit and produces a 1 where the bits differ. It has three properties that solve this problem:

    • x ^ x = 0: a number XORed with itself disappears.
    • x ^ 0 = x: XOR with zero leaves a number unchanged.
    • It doesn't matter in which order the numbers are combined, or how they are grouped.

    If you XOR every element of the array together, the order doesn't matter, so you can regroup the elements so that equal ones sit next to each other. Each pair becomes 0, the zeros vanish, and the lone number is all that is left. For [4, 1, 2, 1, 2] the product is 4 ^ 1 ^ 2 ^ 1 ^ 2, which is the same as 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0 = 4.

    The same holds for negative numbers. They are stored in two's complement, which has a definite bit pattern, and x ^ x is 0 for those bits too. For example, -5 ^ 3 ^ 3 is -5.

    Step by step

    1. Create the accumulator. var s = 0 is a mutable Int. It starts at 0 because XOR with 0 leaves the first number as it is.
    2. Loop over the array. for (num <- nums) gives each element in turn.
    3. Fold each number in. s = s ^ num combines the running value with the current number. A pair of equal numbers makes the accumulator return to the value it had before the pair, whatever lies between them.
    4. Return the accumulator. After one pass, s holds the single number.

    The solution in Scala

    class Solution {
    def singleNumber(nums: Array[Int]): Int = {
        var s = 0
        for (num <- nums) {
            s = s ^ num
        }
        return s
    }
}

    The Scala details worth a closer look:

    • ^ is XOR, not a power. Scala has no exponent operator. On integers, ^ is bitwise XOR, the same as in Java.
    • var because it changes. The accumulator is reassigned on every pass, so it is a var. A val would not compile with s = s ^ num.
    • Compound form. s ^= num is the same as s = s ^ num. The lesson uses the long form.
    • Loop over an Array[Int]. for (num <- nums) walks the elements, not the indices. num is an Int.
    • Same type in and out. The method returns Int, and s is an Int, so no conversion is needed. The XOR of two Int values can't overflow, since it never carries between bits.
    • The return keyword. It is outside the loop here, so it is an ordinary return. The bare s as the last line would give the same result.

    Complexity

    Time: O(n). The array is read once, with one XOR per element.

    Space: O(1). One integer accumulator and the loop variable. The array is not modified or copied.

    Edge cases and common mistakes

    • One element. [1] gives 0 ^ 1 = 1.
    • The single number comes first, last or in the middle. The position doesn't matter, because XOR doesn't depend on order. [1, 2, 2], [2, 1, 2] and [2, 2, 1] all give 1.
    • Negative values. [-5, 3, 3] gives -5.
    • Starting the accumulator at something else. Any nonzero start value would stay in the answer. It has to start at 0.
    • Using + or -. Adding or subtracting doesn't cancel pairs. The sum of [2, 2, 1] is 5, not 1.
    • Input that breaks the rule. The method relies on every other value appearing exactly twice. If a value appeared three times, it would not cancel, and the result would not be meaningful. The constraints rule that out.

    Testing

    • nums = [2, 2, 1] returns 1.
    • nums = [4, 1, 2, 1, 2] returns 4.
    • nums = [1] returns 1.
    • nums = [-5, 3, 3] returns -5.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free