Find the number that appears once, and other numbers twice.
MediumXOR everything; pairs cancel
Problem
Given an array of nums of n integers. Every integer in the array appears twice except one integer. Find the number that appeared once in the array.
XOR everything together — identical pairs cancel out, leaving the lonely number.
The idea
XOR is its own inverse, so every value appearing twice cancels to zero and the single value is left standing. It needs one pass and no memory at all, which beats both sorting and a frequency map.
The trick
- x ^ x = 0 and x ^ 0 = x — the two identities that make this work.
- Order does not matter; XOR is commutative and associative.
- O(n) time, O(1) space.
Step 1 of 5. Brute force: count how many times each number appears — the lonely one wins. Values: 1, 1, 2, 2, 3, 4, 4.
Count each number.
1for (let i = 0; i < n; i++) {2 let count = 0;3 for (let j = 0; j < n; j++) if (nums[j] === nums[i]) count++;4 if (count === 1) return nums[i];5}Input
- array
- [1, 1, 2, 2, 3, 4, 4]
Memory
- count
- —
Output
- count
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [1, 1, 2, 2, 3]
- Output:
- 3
- Explanation:
- Everything is paired except 3.
Example 2
- Input:
- nums = [4, 5, 4]
- Output:
- 5
- Explanation:
- 5 is the lonely number.
Example 3
- Input:
- nums = [7]
- Output:
- 7
- Explanation:
- A single element is the answer itself.
Constraints
- 1 <= n <= 10^5
- -3*10^5 <= nums[i] <= 3*10^5
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.