My Java solution in O(n) time complexity and O(1) space complexity using XOR


  • 47
    E
    public class Solution {
        public int singleNumber(int[] nums) {
            int res = 0;
            for(int num : nums) {
                res ^= num;
            }
            return res;
        }
    }

  • 5
    J

    I'm sure for a lot of people this may be confusing as to why this works. The idea hinges on 3 properties of xor. (1) that its a commutative operation (i.e. a xor b = b xor a). (2) that something xor itself is 0. So a xor a = 0. And (3) 0 xor a = a. These three properties mean that

    a xor b xor a = a xor a xor b = 0 xor b = b.

    Thus it doesn't matter the order of the numbers. If something only occurs once it won't get negated.


  • 0
    M

    I wonder if the complexity of this algo is really O(n). It seems like O(n * length of binary number)


  • 0
    E

    We only need to calculate the times that res ^= num; is called. We do not need to know the times of the bit operation for each bit so the time complexity is O(n).


  • 0
    O

    nice explain, thanks


  • 0
    S

    @marrvolo
    The XOR operation is one single machine operation, it doesn't matter the length of binary number.

    Also, in Big O(), O(n) is equivalent as O(x*n), the complexity remains linear which is what we care most of the time.


Log in to reply
 

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