Single Number

easyFREEHash Maps & SetsApple DSA

Given an array where every element appears twice except one, find the single element. Must run in O(n) time and O(1) space.

Example

Input

2,2,1

Output

Reasoning

nums holds the values $2, 2, 1$ , so $n = 3$ . The promise is that every value occurs exactly twice except one value that occurs once, so $n$ is always odd: $n = 2k + 1$ , here $k = 1$ .
Counting occurrences: the value $2$ sits at positions $0$ and $1$ (count $2$ ); the value $1$ sits at position $2$ (count $1$ ).
The answer is the one value whose count is odd, here $v = 1$ , so the output is 1.
The output is a single integer taken from the array itself, not an index or a count. Order is irrelevant: the arrangements 1, 2, 2 or 2, 1, 2 give the same answer.
Notice the limits: $O(n)$ time means each element is looked at a constant number of times, and $O(1)$ space means the extra memory cannot grow with $n$ , so a separate tally for every distinct value is off the table. Values can be negative (down to $-3 \times 10^4$ ), and a one-element array such as $[1]$ just returns its element.

Constraints

1 <= len(nums) <= 3 * 10^4
-3 * 10^4 <= nums[i] <= 3 * 10^4

More from Apple DSA

Happy Numbereasy Longest Consecutive Sequencemedium Path Sumeasy Invert Binary Treeeasy Maximum Depth of Binary Treeeasy

Concept primer

Background Knowledge

The "Single Number" problem is a classic example of a bit manipulation problem. To understand this problem, you need to have a basic understanding of how bits work in computer science. In binary representation, each digit (or bit) can have a value of either 0 or 1. Bitwise operations are used to manipulate these bits. The key concept here is the XOR (exclusive OR) operation, which returns 1 if the two bits are different, and 0 if they are the same. The XOR operation has several useful properties, including $a \oplus 0 = a$ , $a \oplus a = 0$ , and $a \oplus b \oplus a = b$ .

In the context of this problem, we can use the properties of bitwise operations to find the single element in the array. Since every element appears twice except one, we can use the XOR operation to eliminate the elements that appear twice. This is because $a \oplus a = 0$ , so when we XOR all the elements in the array, the elements that appear twice will cancel each other out, leaving only the single element.

The requirement of O(n) time and O(1) space complexity means that we need to find a solution that only iterates through the array once and uses a constant amount of space. This rules out solutions that involve sorting the array or using additional data structures that scale with the size of the input.

Algorithm/Approach

The general approach to solve this type of problem is to use a bit manipulation algorithm that takes advantage of the properties of bitwise operations. Specifically, we can use the XOR operation to eliminate the elements that appear twice and find the single element. This approach is efficient because it only requires a single pass through the array and uses a constant amount of space.

Step-by-Step Strategy

To implement the solution, follow these steps:

Initialize a variable to store the result of the XOR operation. This variable will be used to accumulate the XOR of all the elements in the array.
Iterate through the array, XORing each element with the result variable.
After iterating through the entire array, the result variable will hold the value of the single element.

Common Pitfalls

When implementing the solution, watch out for the following common pitfalls:

Forgetting to initialize the result variable to 0, which is the identity element for the XOR operation.
Using the wrong bitwise operation, such as AND or OR instead of XOR.
Not iterating through the entire array, which can cause some elements to be missed.

Time & Space Complexity

The expected time complexity of the solution is O(n), where n is the number of elements in the array. This is because we only need to iterate through the array once to find the single element. The expected space complexity is O(1), which means the space required does not change with the size of the input array, making it very efficient for large inputs.

solution.py

Python 3.13

Test results