Single Number

easyPROMath & Bit ManipulationDSA for AI Engineers

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 DSA for AI Engineers

Power of Twoeasy Binary Tree Level Order Traversaleasy Flatten Binary Tree to Linked Listmedium Serialize and Deserialize Binary Treehard Coin Changemedium

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results

Single Number

Example

Constraints

More from DSA for AI Engineers

Background Knowledge

Continue the full explanation

Editor locked