Single Number

Leetcode Easy

Problem

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

Solution

class Solution {
    public int singleNumber(int[] nums) {

        for (int i = 1; i < nums.length; i++) {
            nums[i] = nums[i] ^ nums[i-1];
        }

        return nums[nums.length-1];
    }
}

How it works

If you xor (^) 2 (or more) numbers together, the resulting bitstring will represent the difference between the bitstrings. I used this to my advantage to xor all of the numbers together to find the difference between all of them. Since only one number is different and all of the others will cancel out to 0, we will be left with the resulting bitstring.