Simple Java Solution With Linear Time Complexity Using XOR


  • 0
    J

    An XOR operation between two same number returns 0. XOR any number with 0 returns that number.
    So when we XOR all the integers the pair of equal integers will yield 0 and we will be left with XOR between 0 and the single number which will return the single number in the given integer array.

    Truth Table of XOR:

    ^ | 0 1
    --+-----
    0 | 0 1
    1 | 1 0

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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.