Welcome to Subscribe On Youtube
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^{4}
2^{31} <= nums[i] <= 2^{31}  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 builtin “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
andx
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 forx
(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 inx
, theAND
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
is1010
. 
Invert Bits: Inverting all bits gives
0101
. 
Add 1: Adding
1
to0101
results in0110
, which is the binary representation of10
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] } }