260. Single Number III

Description

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.

Solutions

Solution 1: Bitwise Operation

The XOR operation has the following properties:

Any number XOR 0 is still the original number, i.e., $x \oplus 0 = x$;
Any number XOR itself is 0, i.e., $x \oplus x = 0$;

Since all numbers in the array appear twice except for two numbers, we can perform XOR operation on all numbers in the array to get the XOR result of the two numbers that only appear once.

Since these two numbers are not equal, there is at least one bit that is 1 in the XOR result. We can use the lowbit operation to find the lowest bit of 1 in the XOR result, and divide all numbers in the array into two groups based on whether this bit is 1 or not. This way, the two numbers that only appear once are separated into different groups.

Perform XOR operation on each group separately to obtain the two numbers $a$ and $b$ that only appear once.

The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$.

lowbit

The “lowbit” operation, often encountered in the context of binary operations and bitwise manipulation, refers to a method for obtaining the lowest set bit (rightmost bit that is set to 1) of a number. In many programming tasks, especially those involving binary indexed trees or certain bit manipulation algorithms, identifying the lowest set bit is crucial.

There isn’t a built-in “lowbit” function in many programming languages, but it can be easily implemented using basic bitwise operations. The key to finding the lowbit of a number is to isolate the rightmost 1 bit. This can be achieved with the expression x & (-x), where x is the number you’re working with.

Explanation

Given a binary number, its two’s complement is obtained by inverting all the bits and adding 1 to the least significant bit (LSB). In the expression x & (-x), -x is the two’s complement of x. When you AND a number with its two’s complement, all bits other than the rightmost set bit become 0 because:

Every bit to the left of the lowest set bit in x and -x are opposite, so they cancel out to 0.
The lowest set bit in x remains 1, and since it’s the point where we start counting for -x (due to the addition of 1 in two’s complement), it matches and remains 1.
Every bit to the right of the lowest set bit is 0 in x (since it’s the lowest set bit), and therefore, regardless of their values in -x, the AND operation zeroes them out.

Python Example

Here’s a simple Python function that demonstrates how to perform the lowbit operation:

def lowbit(x):
    return x & (-x)

# Example usage
number = 12  # Binary: 1100
print(lowbit(number))  # Output: 4 (Binary: 100)

number = 10  # Binary: 1010
print(lowbit(number))  # Output: 2 (Binary: 10)

number = 18  # Binary: 10010
print(lowbit(number))  # Output: 2 (Binary: 10)

In these examples, the lowbit function correctly identifies the lowest set bit of various numbers, showcasing how the expression x & (-x) effectively isolates this bit. This operation is widely useful in algorithms that require bit manipulation for efficient computation.

Step by Step Example `x = 10`

Let’s take x = 10 as an example:

Binary Representation: The binary representation of 10 is 1010.
Invert Bits: Inverting all bits gives 0101.
Add 1: Adding 1 to 0101 results in 0110, which is the binary representation of -10 in two’s complement.
Perform x & (-x):
- x = 1010 (binary for 10)
- -x = 0110 (binary for -10)
- x & (-x) = 0010

The result 0010 corresponds to the decimal number 2, which is the value of the lowest set bit in 10.

This process demonstrates how x & (-x) isolates the lowest set bit of a number, which is a useful operation in various bit manipulation algorithms and problems.

class Solution {
    public int[] singleNumber(int[] nums) {
        int xs = 0;
        for (int x : nums) {
            xs ^= x;
        }
        int lb = xs & -xs;
        int a = 0;
        for (int x : nums) {
            if ((x & lb) != 0) {
                a ^= x;
            }
        }
        int b = xs ^ a;
        return new int[] {a, b};
    }
}

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        long long xs = 0;
        for (int& x : nums) {
            xs ^= x;
        }
        int lb = xs & -xs;
        int a = 0;
        for (int& x : nums) {
            if (x & lb) {
                a ^= x;
            }
        }
        int b = xs ^ a;
        return {a, b};
    }
};

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:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xs = reduce(xor, nums)
        a = 0
        lb = xs & -xs
        for x in nums:
            if x & lb:
                a ^= x
        b = xs ^ a
        return [a, b]

func singleNumber(nums []int) []int {
	xs := 0
	for _, x := range nums {
		xs ^= x
	}
	lb := xs & -xs
	a := 0
	for _, x := range nums {
		if x&lb != 0 {
			a ^= x
		}
	}
	b := xs ^ a
	return []int{a, b}
}

function singleNumber(nums: number[]): number[] {
    const xs = nums.reduce((a, b) => a ^ b);
    const lb = xs & -xs;
    let a = 0;
    for (const x of nums) {
        if (x & lb) {
            a ^= x;
        }
    }
    const b = xs ^ a;
    return [a, b];
}

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var singleNumber = function (nums) {
    const xs = nums.reduce((a, b) => a ^ b);
    const lb = xs & -xs;
    let a = 0;
    for (const x of nums) {
        if (x & lb) {
            a ^= x;
        }
    }
    const b = xs ^ a;
    return [a, b];
};

public class Solution {
    public int[] SingleNumber(int[] nums) {
        int xs = nums.Aggregate(0, (a, b) => a ^ b);
        int lb = xs & -xs;
        int a = 0;
        foreach(int x in nums) {
            if ((x & lb) != 0) {
                a ^= x;
            }
        }
        int b = xs ^ a;
        return new int[] {a, b};
    }
}

impl Solution {
    pub fn single_number(nums: Vec<i32>) -> Vec<i32> {
        let xs = nums.iter().fold(0, |r, v| r ^ v);
        let lb = xs & -xs;
        let mut a = 0;
        for x in &nums {
            if (x & lb) != 0 {
                a ^= x;
            }
        }
        let b = xs ^ a;
        vec![a, b]
    }
}

260 - Single Number III

260. Single Number III

Description

Solutions

lowbit

Explanation

Python Example

Step by Step Example `x = 10`

All Problems

All Solutions

Welcome to Subscribe On Youtube

260. Single Number III

Description

Solutions

lowbit

Explanation

Python Example

Step by Step Example x = 10

All Problems

All Solutions

Step by Step Example `x = 10`