260. Single Number III
Problem Description
In this problem, we are given an integer array nums
where precisely two elements are unique, appearing only once, and the rest of the elements appear exactly two times. The task is to find the two unique elements without using additional space and ensuring that the algorithm runs in linear time complexity. This means we cannot sort the array or use a data structure that would take up extra space proportional to the input size. The uniqueness of our solution should come from cleverly manipulating the numbers themselves to identify the two that are different from the rest.
Intuition
To solve this problem efficiently, we should utilize the properties of the XOR (^) bitwise operation. When we apply XOR to two identical numbers, the result is zero; when we apply it to a number and zero, we get the original number back. These properties are crucial:
- If we XOR a number with itself, we get 0 ().
- Any number XORed with 0 remains unchanged ().
When we XOR all numbers in the array, we are left with the XOR of the two unique numbers, since all other numbers cancel each other out (pairwise XORing them gives us 0).
Now, since the two unique numbers are distinct, their XOR result must have at least one bit set to 1, representing a place where they differ. If we can isolate this bit, we can divide all numbers in the array into two groups, based on whether they have this bit set to 1 or not. This step ensures that each group contains exactly one of the unique numbers, with all others still forming cancelling pairs.
We obtain such a bit using xs & -xs
, which isolates the lowest bit that is set to 1 in the XOR result.
With this bit as a mask, we iterate through all the numbers again, using the mask to split the numbers into two groups and performing XOR in each group to find the unique numbers. We are guaranteed that:
- All duplicates will still cancel out within their respective groups.
- The two unique numbers will fall into separate groups and won't cancel out.
- The final result of the XOR operation in each group is the unique number within that group.
Thus, this process leaves us with the two numbers that appear only once in the array, meeting our time and space complexity requirements.
Solution Approach
The solution uses the bitwise XOR operation to pinpoint the two unique numbers in the array. The XOR operation is chosen for its ability to cancel out pairs of identical numbers, meaning that XOR-ing all numbers in an array where each number appears twice, except for two numbers, will leave us with the XOR of these two unique numbers.
Here are the steps to this approach, using bitwise operations in Python:
-
We first apply XOR to all the elements in the array, which is conveniently done using the
reduce()
function with thexor
operator from Python's functools module. The result of this operation is stored in variablexs
and can be mathematically represented as:xs = nums[0] ^ nums[1] ^ ... ^ nums[n - 1]
Since XOR-ing a number with itself results in 0, and any number XOR-ed with 0 is the number itself, all paired numbers cancel each other, and we are left with:
xs = unique1 ^ unique2
-
We need to find a way to separate
unique1
andunique2
. Since they are distinct, there must be at least one bit in which they differ. The line of codelb = xs & -xs
finds the least significant bit that is set to 1 in the XOR result (xs
). The-xs
is a way to get the two's complement which flips all the bits ofxs
and adds 1, so when itās AND-ed withxs
, all the bits are canceled out except for the least significant bit. -
With this bit (
lb
), we divide the numbers into two groups and XOR the numbers in each group to find the unique numbers. This step is done by iterating through the array again with:for x in nums: if x & lb: a ^= x
This code XORs all numbers that have the
lb
bit set. Since all other numbers appear twice, onlyunique1
orunique2
(whichever has that bit set) will be the result of this XOR operation (a
holds this unique number). -
To find the second unique number, XOR
a
withxs
:b = xs ^ a
Since
xs
isunique1 ^ unique2
, by XOR-ing it with one unique number, the other is revealed, giving usb
, the second unique number.
The final result, [a, b]
, contains the two numbers that occur only once in the array. The use of bitwise operations, along with the loop through the array, ensures that the algorithm runs in linear time, O(n), with constant space complexity, O(1), as it employs a fixed number of integer variables regardless of the input size.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let us take an array nums = [4, 1, 2, 1, 2, 3]
to illustrate the solution approach.
-
We apply XOR to all elements:
xs = 4 ^ 1 ^ 2 ^ 1 ^ 2 ^ 3
After applying XOR successively, we get:
xs = 4
This is because 1 ^ 1 and 2 ^ 2 both give 0, and XOR-ing 0 with any number yields that number. Thus, all duplicates cancel each other, and we're left with the XOR of the two unique numbers (
xs = 4 ^ 3
). -
Find the least significant bit that is set to 1:
xs = 4 ^ 3 # which is 7 in binary (0111) lb = 7 & -7 # which isolates the least significant bit (0001)
The result
lb
is 1, indicating the least significant bit that is different between the two unique numbers (4 and 3). -
We now divide the numbers into two groups and XOR them separately based on the least significant bit set to 1:
a = 0 b = 0 for x in nums: if x & lb: a ^= x # This will be the group where the least significant bit is 1 else: b ^= x # This will be the group where the least significant bit is 0
Upon iterating (4 has the least significant bit 0, 3 has it set to 1):
a = 3 (as 1^1 = 0, 2^2 = 0, leaving 3) b = 4 (as it is the only number remaining with least significant bit 0)
After the loop,
a
holds the value3
, andb
holds the value4
. -
Since
a
holds one of the unique numbers, there is no need for the final XOR step to determineb
. If we had not directly received the second unique number, we would XORa
withxs
to findb
:# b = xs ^ a (only necessary if b was not directly received from the loop)
The final result is [3, 4]
, which contains the two unique numbers from the array. This example illustrates how the bitwise XOR and AND operations can be used to solve the problem efficiently, adhering to both time and space complexity constraints.
Solution Implementation
1from functools import reduce
2from operator import xor
3from typing import List
4
5class Solution:
6 def singleNumber(self, nums: List[int]) -> List[int]:
7 # Calculate the XOR of all the numbers, the result will be the XOR of
8 # the two unique numbers as other numbers appear twice and thus cancel out.
9 xor_all_nums = reduce(xor, nums)
10
11 # Find the rightmost set bit in xor_all_nums by & with its two's complement.
12 # This bit will be different in the two unique numbers, so we can use it
13 # to distinguish between the two groups.
14 rightmost_set_bit = xor_all_nums & -xor_all_nums
15
16 unique_num_1 = 0
17 # Loop through all numbers and XOR those with the rightmost set bit.
18 # This isolates one of the unique numbers due to the bitwise & filter.
19 for num in nums:
20 if num & rightmost_set_bit:
21 unique_num_1 ^= num
22
23 # Find the second unique number by XORing the first unique number
24 # with xor_all_nums (which is the XOR of the two unique numbers).
25 unique_num_2 = xor_all_nums ^ unique_num_1
26
27 # Return the list containing the two unique numbers.
28 return [unique_num_1, unique_num_2]
29
1class Solution {
2 public int[] singleNumber(int[] nums) {
3 // Initial bitmask value which will eventually contain the XOR of all numbers in the array
4 int xorResult = 0;
5 // Perform XOR across all elements in the array to find the XOR of the two unique numbers
6 for (int num : nums) {
7 xorResult ^= num;
8 }
9
10 // Get the rightmost set bit in xorResult which will differentiate the two unique numbers
11 // Negating xorResult gives its two's complement, and bitwise AND with original number
12 // isolates the rightmost set bit
13 int rightmostSetBit = xorResult & -xorResult;
14
15 int firstUniqueNumber = 0;
16 // XOR the numbers that have the set bit (same as in rightmostSetBit)
17 // to find one of the unique numbers
18 for (int num : nums) {
19 // Check if the bit is set
20 if ((num & rightmostSetBit) != 0) {
21 firstUniqueNumber ^= num;
22 }
23 }
24
25 // XOR the found unique number with xorResult to find the second unique number since
26 // xorResult is a XOR of both unique numbers
27 int secondUniqueNumber = xorResult ^ firstUniqueNumber;
28
29 // Return an array containing both unique numbers
30 return new int[] {firstUniqueNumber, secondUniqueNumber};
31 }
32}
33
1#include <vector>
2
3class Solution {
4public:
5 std::vector<int> singleNumber(std::vector<int>& nums) {
6 // Initial total XOR value for all numbers in the array
7 long long total_xor = 0;
8 for (int num : nums) {
9 total_xor ^= num;
10 }
11
12 // Find the rightmost set bit in the total XOR (first bit that differs between the two unique numbers)
13 int last_bit = total_xor & -total_xor;
14
15 int num1 = 0;
16 for (int num : nums) {
17 // Separate numbers into two groups and find the first unique number by XORing numbers in the same group
18 if (num & last_bit) {
19 num1 ^= num;
20 }
21 }
22
23 // The second unique number is found by XORing the first unique number with the initial total XOR
24 int num2 = total_xor ^ num1;
25
26 // Return the two unique numbers
27 return {num1, num2};
28 }
29};
30
1function singleNumber(nums: number[]): number[] {
2 // Perform XOR on all numbers to get the XOR of the two unique numbers.
3 const xorOfUniqueNums = nums.reduce((accumulated, current) => accumulated ^ current);
4
5 // Get the rightmost set bit in xorOfUniqueNums. This bit will be set in one unique number and not in the other.
6 const rightmostSetBit = xorOfUniqueNums & -xorOfUniqueNums;
7
8 let firstUniqueNumber = 0;
9
10 // Iterate through all numbers to separate them into two groups and perform XOR.
11 // The groups are based on whether they have the rightmost set bit.
12 for (const num of nums) {
13 if (num & rightmostSetBit) {
14 // XOR numbers that have the rightmost set bit.
15 // The result will be one of the unique numbers.
16 firstUniqueNumber ^= num;
17 }
18 }
19
20 // XOR the first unique number with xorOfUniqueNums to get the second unique number.
21 const secondUniqueNumber = xorOfUniqueNums ^ firstUniqueNumber;
22
23 // Return the two unique numbers.
24 return [firstUniqueNumber, secondUniqueNumber];
25}
26
Time and Space Complexity
The time complexity of the code is O(n)
, where n
is the length of the array nums
. This is because there is a single loop in the function that iterates over all the elements in the array exactly once to find the numbers that appear just once.
For the space complexity, it is O(1)
which signifies constant space usage. Outside of the input array, the code only uses a fixed number of integer variables (xs
, a
, lb
, b
), irrespective of the input size, hence the space used does not scale with the size of the input array.
Learn more about how to find time and space complexity quickly using problem constraints.
Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!