260. Single Number III - LeetCode Fastest Solution

Hello Code Recipian! Welcome back to another leetcode problem solutions article. In our previous article we discussed the solution to LeetCode 136. Single Number. Today we will be solving a variation of this problem 260. Single Number III. This is a very popular FAANG interview question.

If you have not yet gone through our article on 136. Single Number, we recommend you to go through that one first, it will help you establish a solid base to solve this problem.

Problem Statement: Single Number III

Given an integer array nums, every element in nums appears exactly twice except for two numbers that appear only once. Find these two numbers. You can return the answer in any order.

You must write an algorithm that runs in linear time and uses only constant extra space.

Example 1:

Input: [1, 4, 2, 1, 3, 5, 6, 2, 3, 5]
Output: [4, 6]
Explanation: 4 and 6 appear only once in the input array.

Example 2:

Input: [1, 2, 1, 3, 2, 5]
Output: [3, 5]

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.

Solution

For solving the Single Number problem we used the XOR approach. To solve this problem as well, we can use the same XOR approach with a slight modification.

Before we begin, a quick recap on XOR properties:

1. If we XOR a number with itself, we get 0.

2. If we XOR a number with 0, we get back the same number.

Algorithm

Below is a step-by-step explanation for the working of the algorithm:

1. Initialization:

   Create a variable num1XorNum2, and initialize it with the value of the first element in nums array.

2. Perform XOR on all elements in nums:

   1. Iterate through the nums array from start to end.

   2. In each iteration we perform the XOR of the current element with num1XorNum2.

   3. Perform step b for all elements in nums. At the end of step b, all numbers that appear twice cancel each other out, leaving behind the XOR of only two numbers that appear only once, and at the end of step 2 this is what will be stored in num1XorNum2.

3. Separate Num1 and Num2:

   In order to return the result, we need to separate out num1 and num2 from num1XorNum2. How can we do this?

   
   

   We know num1 != num2. If we think logically, if num1 and num2 are different, at least one of the bits in these numbers must be different. If we can find out any one bit in these 2 numbers which is different, we can use this information to separate them into two different buckets or groups based on whether this bit is set or not set (1 or 0), thereby placing num1 and num2 along with other numbers in two different buckets. Then we can perform XOR independently on these two groups leaving behind only num1 and num2.

   
   

   Separating num1 and num2 is done in 2 parts. Let's discuss each of these steps in detail:

   1. Find out the set bit in num1XORNum2:

      1. So, our first task to find out any one bit in num1XorNum2 which is set (or 1). The logic behind doing this is, XOR returns a set bit only when the other bit is different (only 0 1 =1 and 1 0 = 1). So if we can somehow find a set bit in num1XorNum2 we know for sure that, this particular bit is different in both num1 and num2 (since num1XorNum2 is an XOR of num1 and num2).

      2. We can find out the set bit by using AND operator properties.

         

         As you can see AND operation returns 1, only one both are one. We can use this to our advantage to determine the set bit (1 bit) in num1XorNum2.

      3. We just need to find any one of the set bit in num1XorNum2, it can be in any position. For the sake of simplicity, we will find the right most set bit in num1XorNum2.

      4. For this we create a variable rightMostSetBit and initialize it to 1. Next we perform AND operation on num1XorNum2 and rightMostSetBit.

         1. If it is not a set bit it will return 0.

         2. If it is a set bit it will return a non-zero result.

      5. We check every bit in num1XorNum2 by left shifting rightMostSetBit in each iteration.

   2. Put numbers into two separate groups:

      1. Once we know the set bit in num1XorNum2, next step is to group numbers in nums based on this bit.

         1. All numbers in nums that have this bit set are put in one group.

         2. All numbers in nums that have this bit not set, we put in another group.

      2. With numbers divided into two groups, half of the numbers in nums including num1 are now placed in one group and other half including num2 are placed in another group.

      3. Now if we take the XOR of numbers in these two groups separately, since num1 and num2 in two different groups, all numbers in each group that appear twice will cancel each other out and num1 and num2 will be left behind.

4. Return result: Now we have separated num1 and num2. These are the two numbers which appear only once in nums, and this is our required result.

Simulation

Below is a pictorial depiction of the working of the algorithm:

Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses:

1. Udemy Video Tutorials - Available at 95% off

2. System Design Interview Complete Guide

3. Cracking The Coding Interview - Most Preferred Book For Coding Interviews

4. Data Structures And Algorithms - A Complete Guide 

5. Learn In-Demand Tech Skills And Stay Ahead Of Others

Code

Go Solution

Python Solution

Java Solution

JavaScript Solution

TypeScript Solution

C++ Solution

C# Solution

C Solution

PHP Solution

Kotlin Solution

Swift Solution

Ruby Solution

Rust Solution

Scala Solution

Complexity Analysis

Time Complexity

First loop:

In the first loop we iterate through all the elements of the array to calculate XOR of elements. This has a time complexity of O(n).

Second loop:

The second loop runs until a set bit is found. In the worst case, when the maximum size of the number can go upto 32 bits (from problem constraints). So, in the worst case the loop will iterate upto 32 times, so it has a constant time complexity of O(1).

Third Loop:

The third loop also iterates through the entire array once again to perform XOR. This also has a time complexity of O(n).

Therefore, the overall time complexity of this algorithm is O(n) + O(1) + O(n) = O(n).

Space Complexity

Space complexity for this solution is O(1) as we are not using any extra space.

That brings us to the end of this article. We appreciate the time you have taken to read through it. If you have any questions, feel free to ask them in the comments below. We're here to help and will gladly answer your queries.

If you enjoyed this article, please subscribe to our website and Youtube channel. Your support inspires us to bring out more such articles in future.

Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section. There's a wealth of knowledge waiting for you there!

Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now.

Follow us: YouTube, Facebook, Twitter, LinkedIn, Tumblr, Instagram.