Python solution with detailed explanation


  • 0
    G

    Solution

    Single Number III https://leetcode.com/problems/single-number-iii/

    Algorithm

    1. Important nugget: Since we can easily get the rightmost set bit, let us use it:
      set_bit_no = xor & ~(xor-1) = (1110) & ~(1101) = 0010
      http://www.geeksforgeeks.org/find-two-non-repeating-elements-in-an-array-of-repeating-elements/
      All the bits that are set in xor will be set in one non-repeating element (x or y) and not in other. So if we take any set bit of xor and divide the elements of the array in two sets – one set of elements with same bit set and other set with same bit not set. By doing so, we will get x in one set and y in another set. Now if we do XOR of all the elements in first set, we will get first non-repeating element, and by doing same in other set we will get the second non-repeating element.

    Let us see an example.
    arr[] = {2, 4, 7, 9, 2, 4}

    1. Get the XOR of all the elements.
      xor = 2^4^7^9^2^4 = 14 (1110)
    2. Get a number which has only one set bit of the xor.
      Since we can easily get the rightmost set bit, let us use it.
      set_bit_no = xor & ~(xor-1) = (1110) & ~(1101) = 0010
      Now set_bit_no will have only set as rightmost set bit of xor.
    3. Now divide the elements in two sets and do xor of
      elements in each set, and we get the non-repeating
      elements 7 and 9. Please see implementation for this
      step.
    class Solution(object):
        def singleNumber(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            xor = 0
            for x in nums:
                xor = xor ^ x
            mask = xor & ~(xor-1)
            x,y = 0,0
            for n in nums:
                if n & mask:
                    x = x ^ n
                else:
                    y = y ^ n
            return [x,y]
    

Log in to reply
 

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