title: Single Number
tags:
- single-number
- No.136
- simple
- boolean-algebra
- bit
- array
Description
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,1]
Output: 1
Example 2:
Input: [4,1,2,1,2]
Output: 4
Corner Cases
"""a"","
Solutions
XOR Operation
XOR operation satisfies the law of association: (a ^ b) ^ c == a ^ (b ^ c)
Besides, since the truth table is:
| 0 | 1 | |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
Thus all pairs of the same number are reduced to zero.
The running time is O(n) with O(1) space complexity.
class Solution {
public int singleNumber(int[] nums) {
int xor = nums[0];
for (int i=1; i<nums.length; i++) {
xor = xor ^ nums[i];
}
return xor;
}
}
