Question

Formatted question description: https://leetcode.ca/all/260.html

/**
 260	Single Number III

 Given an array of numbers nums, in which
    exactly two elements appear only once and
    all the other elements appear exactly twice.

 Find the two elements that appear only once.

 Example:

 Input:  [1,2,1,3,2,5]
 Output: [3,5]

 Note:
 The order of the result is not important. So in the above example, [5, 3] is also correct.
 Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

 */

Algorithm

This question is actually a very clever use of the Single Number solution, because that solution can accurately find a number that appears only once, but the premise is that other numbers must appear twice.

And this question has two numbers that only appear once, so if we can find a way to divide the original array into two small arrays, the two different numbers are in the two small arrays, so that the Single Number solution is called separately You can get the answer.

So how to achieve it, first we XOR all the original array, then we will get a number, this number is the result of the XOR of two different numbers, we take out any one of the bits that is ‘1’, For the sake of convenience, we use a &= -a to take out the bit whose rightmost end is ‘1’, specifically how to operate this.

Take the example in the title, if we exclusive OR all of them, we know that the exclusive OR of the same two numbers is 0, then the two 1, and the two 2 are cancelled out, and there is nothing left 3 and 5’exclusive OR’, which is the binary 11 and 101’exclusive OR’, get 110.

Then we perform a &= -a operation. First change the negative number. In binary, the negative number is in the form of complement, and the complement is the complement +1, then the complement of 110 is 11...1001, then after adding 1, it is 11...1010, and then 110 And, get 10, which is the diff variable in the code.

With this diff, the original array can be divided into two arrays. Why, if two identical numbers are XOR, each of them will be 0, and different numbers will be XOR, there must be different corresponding bits, one 0 and one 1, so XOR ‘ it’s 1.

For example, the binary 11 and 101 of 3 and 5, if you look from low to high, the first difference is the second digit. Then we use the second digit to AND each number in the array. Depending on the result, it must be possible to distinguish 3 and 5, and because the other numbers appear in pairs, they are also paired. In the end, they will be XORed into 0, and 3 and 5 will not be affected. XOR the numbers in the two groups separately to get the final result.

Code

public class Single_Number_III {

    public static void main(String[] args) {

        int a = 7;
        int b = a & -a;

        System.out.println(Integer.toBinaryString(a)); // 111

        // to negative, flip bits, and then +1
        System.out.println(Integer.toBinaryString(-a)); //32 bits: 11111111111111111111111111111001
        System.out.println(Integer.toBinaryString(b));

    }

    public class Solution {
        public int[] singleNumber(int[] nums) {

            if (nums == null || nums.length == 0) {
                return new int[]{};
            }

            // Pass 1 :
            // Get the XOR of the two numbers we need to find
            int diff = 0;
            for (int num : nums) {
                diff ^= num;
            }

            diff &= -diff;

            // Pass 2 : diff will distinguish two wanted numbers
            int[] rets = {0, 0}; // this array stores the two numbers we will return
            for (int num : nums) {
                if ((num & diff) == 0) { // the bit is not set
                    rets[0] ^= num;
                } else { // the bit is set
                    rets[1] ^= num;
                }
            }
            return rets;
        }
    }

}

############

class Solution {
    public int[] singleNumber(int[] nums) {
        int eor = 0;
        for (int x : nums) {
            eor ^= x;
        }
        int lowbit = eor & (-eor);
        int[] ans = new int[2];
        for (int x : nums) {
            if ((x & lowbit) == 0) {
                ans[0] ^= x;
            }
        }
        ans[1] = eor ^ ans[0];
        return ans;
    }
}

// OJ: https://leetcode.com/problems/single-number-iii/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    vector<int> singleNumber(vector<int>& A) {
        int x = 0;
        for (int n : A) x ^= n;
        int lb = x & -(unsigned)x, a = 0;
        for (int n : A) {
            if (n & lb) a ^= n;
        }
        return {a, x ^ a};
    }
};

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        eor = 0
        for x in nums:
            eor ^= x
        lowbit = eor & (-eor)
        ans = [0, 0]
        for x in nums:
            if (x & lowbit) == 0:
                ans[0] ^= x
            else:
                ans[1] ^= x
        return ans

############

class Solution(object):
  def singleNumber(self, nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    xor = 0
    for num in nums:
      xor ^= num

    xor = xor & -xor
    a, b = 0, 0
    for num in nums:
      if num & xor:
        a ^= num
      else:
        b ^= num

    return a, b

func singleNumber(nums []int) []int {
	eor := 0
	for _, x := range nums {
		eor ^= x
	}
	lowbit := eor & (-eor)
	ans := make([]int, 2)
	for _, x := range nums {
		if (x & lowbit) == 0 {
			ans[0] ^= x
		}
	}
	ans[1] = eor ^ ans[0]
	return ans
}

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var singleNumber = function (nums) {
    let eor = 0;
    for (const x of nums) {
        eor ^= x;
    }
    const lowbit = eor & -eor;
    let ans = [0];
    for (const x of nums) {
        if ((x & lowbit) == 0) {
            ans[0] ^= x;
        }
    }
    ans.push(eor ^ ans[0]);
    return ans;
};

260 - Single Number III

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions