How do you approach Single Number?

Think about the XOR operation and its properties.

What is the optimal solution to Single Number?

XOR. XOR has two key properties: a ^ a = 0 (same number XORed with itself is 0) a ^ 0 = a (any number XORed with 0 is itself) XOR all numbers together. Pairs cancel out, leaving only the single number.

What is the time complexity of Single Number?

Time complexity: O(n). Space complexity: O(1).

What are common mistakes on Single Number?

Shifting by at least the word width, which is undefined or wraps depending on the language. Using an arithmetic right shift where a logical one is meant - the sign bit propagates and the loop never ends. Precedence: & and | bind more loosely than the comparison operators, so a & 1 == 0 does not mean what it looks like.

gitGood.dev

← Back to problems

Single Number

EasyAlgorithms

Description

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

You must implement a solution with a linear runtime complexity and use only constant extra space.

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

Single Number: approach, complexity and pitfalls

An easy bit manipulation problem, graded against 6 test cases (3 of them hidden).

The pattern: Bit Manipulation

XOR, masks, and shifts - constant-space tricks for counting and pairing.

Reach for it when you see: "Appears once/twice", powers of two, or an explicit O(1) space requirement.

If you are stuck

Show the 3-step hint ladder

Think about the XOR operation and its properties.
XOR of a number with itself is 0, and XOR of a number with 0 is the number itself.
XOR all numbers together - pairs will cancel out, leaving the single number.

The optimal approach

Show the approach: XOR

XOR has two key properties:

1. a ^ a = 0 (same number XORed with itself is 0)

2. a ^ 0 = a (any number XORed with 0 is itself)

XOR all numbers together. Pairs cancel out, leaving only the single number.

Time: O(n)
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Bit Manipulation mistakes

These apply to the pattern as a whole, not just this problem.

Shifting by at least the word width, which is undefined or wraps depending on the language.
Using an arithmetic right shift where a logical one is meant - the sign bit propagates and the loop never ends.
Precedence: `&` and `|` bind more loosely than the comparison operators, so `a & 1 == 0` does not mean what it looks like.

← Back to problems

Single Number

EasyAlgorithms

Description

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

You must implement a solution with a linear runtime complexity and use only constant extra space.

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

Single Number: approach, complexity and pitfalls

An easy bit manipulation problem, graded against 6 test cases (3 of them hidden).

The pattern: Bit Manipulation

XOR, masks, and shifts - constant-space tricks for counting and pairing.

Reach for it when you see: "Appears once/twice", powers of two, or an explicit O(1) space requirement.

If you are stuck

Show the 3-step hint ladder

Think about the XOR operation and its properties.
XOR of a number with itself is 0, and XOR of a number with 0 is the number itself.
XOR all numbers together - pairs will cancel out, leaving the single number.

The optimal approach

Show the approach: XOR

XOR has two key properties:

1. a ^ a = 0 (same number XORed with itself is 0)

2. a ^ 0 = a (any number XORed with 0 is itself)

XOR all numbers together. Pairs cancel out, leaving only the single number.

Time: O(n)
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Bit Manipulation mistakes

These apply to the pattern as a whole, not just this problem.

Shifting by at least the word width, which is undefined or wraps depending on the language.
Using an arithmetic right shift where a logical one is meant - the sign bit propagates and the loop never ends.
Precedence: `&` and `|` bind more loosely than the comparison operators, so `a & 1 == 0` does not mean what it looks like.