Start learning free

LESSON 400 OF 442 · BIT MANIPULATION

Single Number in TypeScript: 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

    TYPESCRIPT · BIT MANIPULATION

    Single Number in TypeScript, explained

    Problem overview

    The method singleNumber receives a non-empty array of integers in which every value appears exactly twice, except for one value that appears once. It returns that single value.

    For nums = [2, 2, 1] the answer is 1. For [4, 1, 2, 1, 2] it is 4, and for [1] it is 1. The lesson asks for O(n) time and O(1) extra space, so sorting the array or counting values in a map is not allowed. The array can also hold negative numbers.

    Approach: XOR cancels the pairs

    The bitwise XOR operator, written ^, combines two numbers bit by bit: each result bit is 1 when exactly one of the two input bits is 1. Two properties solve this problem:

    • x ^ x is 0, because a number cancels itself.
    • x ^ 0 is x, because XOR with 0 changes nothing.

    XOR is also commutative and associative, so the order in which numbers are combined doesn't matter. XOR all the elements of the array together. Every value that appears twice is combined with its twin, wherever the twin sits, and the pair contributes 0. Only the single value has no twin, so the final result is that value.

    For [4, 1, 2, 1, 2] the calculation is 4 ^ 1 ^ 2 ^ 1 ^ 2. Regrouped, it is 4 ^ (1 ^ 1) ^ (2 ^ 2), which is 4 ^ 0 ^ 0, which is 4.

    Step by step

    1. Declare s with let, starting at 0. It is the accumulator. Zero is the neutral element of XOR, so it doesn't disturb the first value.
    2. Loop over nums with for...of, naming each element val.
    3. Assign s = s ^ val in the loop. Each element is folded into the running result.
    4. Return s after the loop.

    The solution in TypeScript

    class Solution {
    singleNumber(nums: number[]): number {
        let s = 0;
        for (const val of nums) {
            s = s ^ val;
        }
        return s;
    }
}

    The TypeScript details worth a closer look:

    • Bitwise operators work on 32-bit integers. A TypeScript number is a double, but ^ first converts both operands to 32-bit signed integers and gives a 32-bit signed result. The lesson's values are within plus or minus 30,000, far inside that range, so nothing is lost. A value beyond 2**31 would be truncated by the conversion, and the answer would be wrong.
    • Negative numbers are fine. Negative integers are stored in two's complement, and the XOR rules still hold. [-3, 5, -3] gives 5, and [-30000, 7, 7] gives -30000.
    • s = s ^ val can be written s ^= val. They mean the same.
    • Inferred types. let s = 0 is inferred as number. The annotation on nums is erased when compiling, so nothing checks at run time that the argument really is an array of numbers.
    • for...of versus for...in. for (const val of nums) gives the values. for...in would give the indexes, as strings.

    Complexity

    Time: O(n). The loop visits each element once and does one XOR per element.

    Space: O(1). The method uses the accumulator and the loop variable, however long the array is.

    Edge cases and common mistakes

    • One element. [1] gives 0 ^ 1, which is 1.
    • The single value is first, last or in the middle. Its position doesn't matter, because the order of XOR doesn't matter. [1, 2, 2], [2, 1, 2] and [2, 2, 1] all return 1.
    • Negative values. The result keeps its sign: [-3, 5, -3] returns 5, and [-1, -1, -5] returns -5.
    • Starting with something other than 0. A different start value would stay mixed into the result.
    • Using + instead of ^. Adding the elements only gives their sum, and nothing cancels. In TypeScript the symbol ^ is XOR, not exponentiation (that is **).
    • Relying on the guarantee. The method only works when every other value appears exactly twice. A value that appears three times would survive the XOR.

    Testing

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