Find Number that appears once
Every value in an array occurs twice except one value that occurs once. Find the unpaired value in linear time using constant extra space.
Work through the cases
3 examplesInput notation
One nonempty line of space-separated integers satisfying this rule.Expected result
The value that appears once.Case 1
Input
5 2 5 8 2
Expected output
8
Case 2
Input
-4
Expected output
-4
Case 3
Input
-1 0 -1
Expected output
0
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
Every number appears twice except one; we need linear time and constant space. A frequency map uses O(n) space. XOR has x\oplus x=0, x\oplus 0=x, and is commutative, so pairing cancels and the leftover is the unique number.
The XOR operation has the following properties:
- Any number XOR 0 is still the original number, i.e., x \oplus 0 = x; - Any number XOR itself is 0, i.e., x \oplus x = 0;
Performing XOR operation on all elements in the array will result in the number that only appears once.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
class Solution {
public int singleNumber(int[] nums) {
int ans = 0;
for (int v : nums) {
ans ^= v;
}
return ans;
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.