260. Single Number III

MediumBit ManipulationArray
Leetcode Link

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:

  1. If we XOR a number with itself, we get 0 (xāŠ•x=0x \oplus x = 0).
  2. Any number XORed with 0 remains unchanged (xāŠ•0=xx \oplus 0 = x).

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:

  1. We first apply XOR to all the elements in the array, which is conveniently done using the reduce() function with the xor operator from Python's functools module. The result of this operation is stored in variable xs 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
  2. We need to find a way to separate unique1 and unique2. Since they are distinct, there must be at least one bit in which they differ. The line of code lb = 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 of xs and adds 1, so when itā€™s AND-ed with xs, all the bits are canceled out except for the least significant bit.

  3. 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, only unique1 or unique2 (whichever has that bit set) will be the result of this XOR operation (a holds this unique number).

  4. To find the second unique number, XOR a with xs:

    b = xs ^ a

    Since xs is unique1 ^ unique2, by XOR-ing it with one unique number, the other is revealed, giving us b, 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 Evaluator

Example Walkthrough

Let us take an array nums = [4, 1, 2, 1, 2, 3] to illustrate the solution approach.

  1. 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).

  2. 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).

  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 value 3, and b holds the value 4.

  4. Since a holds one of the unique numbers, there is no need for the final XOR step to determine b. If we had not directly received the second unique number, we would XOR a with xs to find b:

    # 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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?


Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More