LeetCode | 136. Single Number

Description

Given an array of integers, every element appears twice except for one. Find that single one.
Your algorithm should have a linear run time complexity. Could you implement it without using extra memory?

Solution

This is a classical problem about bitwise "XOR". In JAVA, the operator is "^";

  • For integral types, "&" computes the logical bitwise AND of its operands, "|" means OR, and "^" means XOR.

111 ^ 100 = 011

  • When the two bits are the same, the result of XOR equals 0, otherwise, it equals 1.

0 ^ xxxxx = xxxxx
xxxxx ^ xxxxx = 0

xxxxx ^ yyyyy ^ zzzzz = yyyyy ^ zzzzz ^ xxxxx

//Do not need to consider the order

Code

class Solution {
    public int singleNumber(int[] nums) {
        int len = nums.length;
        int result = 0;
        for(int i = 0; i<len; i++){
            result = result^nums[i];
        }
        return result;
    }
}
Comments
Write a Comment