Question

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

Given an integer array 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. You can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

Example 1:

Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation:  [5, 3] is also a valid answer.

Example 2:

Input: nums = [-1,0]
Output: [-1,0]

Example 3:

Input: nums = [0,1]
Output: [1,0]

Constraints:

2 <= nums.length <= 3 * 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
Each integer in nums will appear twice, only two integers will appear once.

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.

Summarize:

Initialize a variable eor (bitwise XOR) to 0.
Iterate through each number x in nums and perform bitwise XOR with eor. This will result in eor storing the XOR of the two non-repeating numbers.
Find the lowest set bit (lowbit) in eor using the expression lowbit = eor & (-eor). This will give a number with only the lowest set bit of eor set to 1, and all other bits set to 0.
Initialize a list ans with two elements, both initially set to 0.
Iterate through each number x in nums again:
If (x & lowbit) == 0, it means the lowest set bit of x is different from the lowest set bit of eor. Therefore, x belongs to one group of non-repeating numbers. Perform bitwise XOR with ans[0] to find one non-repeating number.
Otherwise, (x & lowbit) != 0, indicating that x belongs to the other group of non-repeating numbers. Perform bitwise XOR with ans[1] to find the other non-repeating number.
Return the ans list containing the two non-repeating numbers.

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