Given a list of numbers in which every number appear twice except one. Return that number

user_5181140 0
Viewed 829

I was asked to find out the number from a list of numbers in Python that is present only once inside the list. As usual, I could easily solve it using the normal method that immediately comes out:


    class Solution(object):
        def singleNumber(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            for i in nums:
                if(nums.count(i) == 1):
                    return i
            return nums[0]

Trying to find out another better way, Internet suggested me to use Bitwise XOR operation and provided the following code which was way faster and more efficient. Below is the code:


    class Solution(object):
        def singleNumber(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            a = 0
            for i in nums:
                a^=i
                print(a)
            return a

The logic was if we do a XOR operation on 2 same bits(0,0 or 1,1) the answer will always be 0 and it will be 1 if the bits are different. Using this, it came out with such an approach.

My mind bogs down at trying to realize how is the normal concept of XOR operation coming to be useful here! I understand the logic they said about that same and different bits but by their code, every time I perform a XOR with the next bit a new number pops out so how can then we guarantee that only the number which occurs once will be evolved?

I feel clueless. It might not be a good approach to have posted a code snippet and then ask for an explanation but I feel the solution is extremely intriguing and am dying to learn how bitwise XOR helped out! Please help if anyone has an idea! Thanks in advance.

Note : In the list, all numbers occur twice except for one.

bitwise-xor xor unique python
3 Answers

The general constraints for this XOR solution are a bit different:

You have a list where exactly one number occurs an odd number of times and all other numbers occur an even number of times and need to find the odd one.

XOR flips the bits if they are identical:

b1 XOR b1 > b0
b0 XOR b0 > b0
b1 XOR b0 > b1
b0 XOR b1 > b1

You have an arbitrary start value (the first number in your list), f.e.:

01010111011111101

If all other numbers occur an even number of times, you see each bit pattern at least twice.

The first time you have pairs of bits and

  • flip every 0,1 bit to 1
  • flip every 1,0 bit to 1
  • flip every 1,1 bit to 0

then you encounter the same number again (because number even times in it):

  • you have a 1 bit from last flipping and encounter a 1 bit again so you flip to 0
  • you have a 1 bit from last flipping and encounter a 0 bit again so you stay at 1
  • you have a 0 bit from last flipping and encounter a 1 bit again so you flip to 1

and you are now back at your original number because even times occuring numbers cancel out:

    101010010
xor 101010010
-------------
    000000000

and if you XOR any other number with 000000000 you get exactly that other number back.

user_75053950

I think without knowing the properties of XOR operation, it is difficult to understand what that code does

This is the property of XOR operation

If the bits are the same, the result is 0. If the bits are different, the result is 1.

Below table will give a clear idea of the above XOR property.

+---+---+---------+
| a | b | a XOR b |
+---+---+---------+
| 0 | 0 |    0    |
| 0 | 1 |    1    |
| 1 | 0 |    1    |
| 1 | 1 |    0    |
+---+---+---------+

The Solution to your question is based on this concept.

An interesting property of XOR is that

  • when you XOR the same number by itself even number of times you get a Zero
  • when you XOR the same number by itself odd number of times you get the number itself

Take for example - Number 2 (2 in binary is - 0010)

Let us

  • Perform XOR of 2 (even no. times)

    0010
0010
----
0000   <- XOR (Value is 0)

  • Perform XOR of 2 (odd number of times)

    0010
0010
0010
----
0010   <- XOR (Value is 2)

Whatever numbers are occuring for even number of times will eventually result in a Zero and Zero XORed with the number occuring odd number of times will give you the same number (that occurs odd number of times)

And the reason why a is initialized to 0 is because - 0 XOR x will give x itself

Say x = 3

0 -> 0000
3 -> 0011
     ----
     0011  <- XOR (Value is 3)

Edit - Based on OP's doubt

For the input arr = [1,2,2,4,1] you are asking why you are getting arbitrary values - 1,3,1,5,4

They are not arbitrary. They are the result of XOR operation between a and i.

Initial value of a = 0

  • First Iteration: i = 1(0001); a = 0 (0000) 
     i: 0000
 a: 0001
    ----
    0001   -> Decimal value is 1 stored in a
  • Second Iteration: i = 2(0010); a = 1 (0001) 
      i: 0010
  a: 0001
     ----
     0011   -> Decimal value is 3 stored in a
  • Third Iteration: i = 2(0010); a = 3 (0011) 
      i: 0010
  a: 0011
     ----
     0001   -> Decimal value is 1 stored in a
  • Fourth Iteration: i = 4(0100); a = 1 (0001) 
      i: 0100
  a: 0001
     ----
     0101   -> Decimal value is 5 stored in a
  • Fifth Iteration: i = 1(0001); a = 5 (0101) 
      i: 0001
  a: 0101
     ----
     0100   -> Decimal value is 4 stored in a
user_27732060

The relevant properties of the XOR operation are:

So consider what happens when your input list is like [3, 4, 5, 4, 3]. From the first two properties, we have that (((3 ^ 4) ^ 5) ^ 4) ^ 3 is the same as (3 ^ 3) ^ (4 ^ 4) ^ 5, from the fourth property this is the same as 0 ^ 0 ^ 5, and from the third property the result is 5. Effectively, every element which appears an even number of times cancels out with itself, leaving just the element which occurs once (or an odd number of times).

user_122990000
Related