Leetcode 260. Single Number III

Problem Explanation:

Let's understand the problem clearly. We are given an array of numbers in which each number appears exactly twice except for two numbers which appear only once. Our job is to find these two numbers. One important requirement the problem sets is we need to solve it with linear time complexity (O(n)) and constant space complexity (O(1)).

Walkthrough Example:

Let's think of an example to demonstrate how the problem works.

1Consider the array [1,2,1,3,2,5]
2Here, the numbers 3 and 5 are the ones which appear only once.

Note: The order of the result is not important. Hence, [5, 3] would also be a correct output.

Approach to the Solution:

The algorithm for this problem can be solved using bit manipulation. We first XOR all the numbers of the array, this will give us a result which is the XOR of the two non-repeating numbers. Next, we find a set bit in this XOR'd result. This set bit indicates different bits in our two non-repeating numbers. Now, we divide all numbers of the array in two sets. One set includes all numbers with the same bit set as our found bit and another set with the same bit not set. These two sets will include one non-repeating number each. Now, we just use XOR in each set separately to get both non-repeating numbers.

Let's take our previous example, following are these steps :

1. XOR all the numbers of array [1,2,1,3,2,5], we get XOR = 6 (which is XOR of 3 and 5)
2. Find a set bit in the XOR (using XOR & -XOR), we get bit = 2 (means second bit from right is set)
3. Now, divide numbers of array in two sets
   • one set of numbers with second bit set i.e., [2,2,6]
   • other set of numbers with bit not set i.e., [1,1,3]
4. Do XOR for each set separately, we get our two non-repeating numbers i.e., [5 and 3]

C++ Solution:

1
2cpp
3class Solution {
4public:
5    vector<int> singleNumber(vector<int>& nums) {
6        int aXorB = 0;
7        // XOR all numbers to get XOR of the non-repeating numbers
8        for(int num : nums) {
9            aXorB ^= num;
10        }
11        // Get set bit in the XOR
12        int setBit = aXorB & (-aXorB);
13        int a = 0;
14        int b = 0;
15        // Divide numbers in two sets and get non-repeating numbers separately
16        for(int num : nums) {
17            if(num & setBit)
18                a ^= num;
19            else
20                b ^= num;
21        }
22        return vector<int>{a, b};
23    }
24};

Python Solution:

1
2python
3class Solution:
4    def singleNumber(self, nums: List[int]) -> List[int]:
5        aXorB = 0
6        # XOR all numbers to get XOR of the non-repeating numbers
7        for num in nums:
8            aXorB ^= num
9        # Get set bit in the XOR
10        setBit = aXorB & (-aXorB)
11        a = 0
12        b = 0
13        # Divide numbers in two sets and get non-repeating numbers separately
14        for num in nums:
15            if num & setBit:
16                a ^= num
17            else:
18                b ^= num
19        return [a, b]

Java Solution:

1
2java
3class Solution {
4    public int[] singleNumber(int[] nums) {
5        int aXorB = 0;
6        // XOR all numbers to get XOR of the non-repeating numbers
7        for (int num : nums) {
8            aXorB ^= num;
9        }
10        // Get set bit in the XOR
11        int setBit = aXorB & (-aXorB);
12        int a = 0;
13        int b = 0;
14        // Divide numbers in two sets and get non-repeating numbers separately
15        for (int num : nums) {
16            if ((num & setBit) != 0) {
17                a ^= num;
18            } else {
19                b ^= num;
20            }
21        }
22        return new int[] {a, b};
23    }
24}

JavaScript Solution:

1
2javascript
3var singleNumber = function(nums) {
4    let aXorB = 0;
5    // XOR all numbers to get XOR of the non-repeating numbers
6    for(let num of nums) {
7        aXorB ^= num;
8    }
9    // Get set bit in the XOR
10    let setBit = aXorB & (-aXorB);
11    let a = 0;
12    let b = 0;
13    // Divide numbers in two sets and get non-repeating numbers separately
14    for(let num of nums) {
15        if(num & setBit)
16            a ^= num;
17        else
18            b ^= num;
19    }
20    return [a, b];
21};

C# Solution:

1
2csharp
3public class Solution {
4    public int[] SingleNumber(int[] nums) {
5        int aXorB = 0;
6        // XOR all numbers to get XOR of the non-repeating numbers
7        foreach(int num in nums) {
8            aXorB ^= num;
9        }
10        // Get set bit in the XOR
11        int setBit = aXorB & (-aXorB);
12        int a = 0;
13        int b = 0;
14        // Divide numbers in two sets and get non-repeating numbers separately
15        foreach(int num in nums) {
16            if((num & setBit) != 0)
17                a ^= num;
18            else
19                b ^= num;
20        }
21        return new int[] {a, b};
22    }
23}

In all these solutions, we first calculate the XOR of all the numbers which equals to the XOR of two non-repeating numbers. We then find a set bit in the XOR result to divide array numbers into two sets. At last, we do XOR for each set separately to get these non-repeating numbers.All the solutions provided above have a time complexity of O(n) because we traverse through the array twice; first to get the XOR of all numbers and then to divide into two sets. The space complexity is O(1) because no extra space is used that scales with the input size.

As we can see, the bit manipulation is a powerful technique for this problem. It allows us to find the two numbers that appear only once in an efficient manner. This problem and solution also highlight the capabilities and potential uses of the XOR operator in many problem-solving situations, especially where we need to find a non-repeating or unique elements in an array.

So, next time when you are stuck with such problems, consider using Bit manipulation techniques. They can be tricky to understand at first, but once grasped, could be your powerful tool in problem-solving.

Remember, algorithms or techniques are no use unless practiced. So, code the solution in all these languages and see the magic of bit manipulation yourself!

Happy coding!