Given an 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?

Thought:

I can do this in Hash table, but that doesn’t meet the requirement ” implement it without using extra memory”

So, Hash table is not a best answer.

I read that operation about bit manipulation last night and that is a fact I found:

**“Two same integers after XOR operation, the value is 0, and 0 XOR any integer is the integer itself”**

So the condition is that “every element appears twice except for one”

So just do XOR for every element in the array, the final result is the integer we are looking for.

1 2 3 4 5 6 7 8 9 |
public class Solution { public int singleNumber(int[] nums) { int result = 0; for (int i = 0; i < nums.length; i++) { result = result ^ nums[i]; } return result; } } |

## Recent Comments