XOR - Java solution


  • 17
    S
    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;
    }
    }

  • 0
    M

    Nice solution. Is this some of the property of the XOR function?. I am sorry but I am bad at bit manipulation. How did you figure out that XOR operation should give the expected answer?


  • 2
    I

    Essentially, this is just a small little trick. The result is effectively equal to the following (num1, num2 and num3 are just elements that appear in nums):

    result = num1 ^ num3 ^ num2 ^ ... ^ unique_num ^ num2 ^ num1 ^ ...

    Because the XOR (^) operator is commutative, we can order the numbers in this expression so that all pairs are next to one another:

    result = num1 ^ num1 ^ num2 ^ num2 ^ num3 ^ num3 ^ ... ^ unique_num

    As you can see, every number has a pair except for the unique number. By the definition of XOR, all of the pairs will XOR down to just a binary string of 0s:

    result = ....0000000 ^ unique_ num = unique_ num

    Thus the result is just unique_num.


  • 0
    S

    @isay

    excuse me I'm not familiar with this XOR operation, but did a little search.
    it says if two numbers are the same, result will be 0,
    but if different, then result will be 1

    I saw you said result=...00000^unique_num=unique_num there.
    so I got confused by this. would you mind explaining this for me? : ) thanks so much!


  • 0
    I

    @stella10 Sure, maybe it was just a little confusing the way I wrote it down. As you said, if the two numbers are the same the result will be 0, so:

    result = (num1 ^ num1) ^ (num2 ^ num2) ^ (num3 ^ num3) ^ ... ^ unique_num = (0) ^ (0) ^ (0) ^ ... ^ unique_num = 0 ^ unique_num = ....0000000 ^ unique_num = unique_num

    I included the trailing 0s (....0000000) in order to emphasize that XOR is a bitwise operation that happens between the corresponding bits of "....00000000" and unique_num. Because 0 XOR 0 = 0 and because 0 XOR 1 = 1, XORing unique_num with this zero bit-string simply preserves unique_num.


  • 0
    S

    @monil1511gmail.com When do the XOR operation between same numbers, the result is 0. For example, "1101" XOR "1101", the result is "0000". Then in this problem, the paired values are eliminated by XOR, and the single value will be left.


Log in to reply
 

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