You get a list of integers nums. Every value in it appears exactly twice, except one. Return the value that appears only once.
Example 1:
Input: nums = [5,3,9,3,5] Output: 9 Explanation: 5 and 3 appear twice. 9 appears only once.
Example 2:
Input: nums = [-4,6,6] Output: -4 Explanation: The value that appears once can be negative.
Example 3:
Input: nums = [12] Output: 12
Constraints:
- 1 to 30,000 numbers.
- Each number is from -30,000 to 30,000.
- Exactly one value appears once.
- Every other value appears exactly twice.
Your algorithm should run in O(n) time and use O(1) extra space.
Hints:
What property can help identify a number that appears only once when all others appear twice?
Think about a bitwise operation that cancels out equal values.
XOR (
^) has two key properties:x ^ x = 0— equal numbers cancel each other outx ^ 0 = x— XOR with 0 leaves the number unchanged
For example:
5 ^ 3 ^ 9 ^ 3 ^ 5 = 9
We iterate through the array once, so the Time Complexity is
O(n).We use only one extra variable, so the Extra Space is
O(1).
Free plan: 30 tutor messages. PRO is unlimited.
Saved
Ctrl + Enter to check
