136. Single Number - LeetCode Fastest Solution

Hello Code Recipian! Another day and we are back with another article on leetcode problem solutions. In this article we will be solving leetcode 136. Single Number. Once you get a good grip of this problem, you should be able to solve advanced level problems like 260. Single Number III, a very popular MAANG interview question.

Let's dive into the problem statement!

Problem Statement: Single Number

Given a non-empty array of unsorted integers nums, every element in nums appears twice except for one number. Find that single number.

Your solution must have a running time complexity of O(n) and use only constant extra space.

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1 

Constraints:

• 1 <= nums.length <= 3 * 10^4

• -3 * 10^4 <= nums[i] <= 3 * 10^4

• Each element in the array appears twice except for one element which appears only once.

Solution

One approach that might straight away come to your mind looking at this problem is to use a hashmap. We can use the hashmap to keep track of the frequencies of each element in input array and using these frequencies we can determine the single number that is missing. But, since we are using hashmap, space complexity of this solution is O(n).

A more effective way to tackle this problem is to utilize the characteristics of bitwise XOR operation.

XOR has the following 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.

Num1	Num2	Num1 XOR Num2
0	0	0
0	1	1
1	0	1
1	1	0

We can take these XOR properties to our advantage in solving the given problem. The idea is simple, we perform XOR operation on all the numbers in the given input array nums. Once we do this, all numbers that appear twice will cancel each other out and we will be left with the number that appears only once.

Let's see how this works in detail.

Algorithm

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

1. Initialization:

   To begin with, we create a result variable to store our result and initialize it with the value of the first element in nums.

2. Find the single number:

   Next, iterate through the nums array from start to end. In each iteration, XOR result with the current number. We must repeat this until we reach the end of array.

3. Return the final result:

   At the end of step 2, we would have performed XOR operation on every number in nums. What this will effectively do is that, all the numbers that appear 2 times in nums will cancel out each other (result will be 0). And the number that appears only once, when XORed with this 0, will give back the same number.

   
   

   Hence, at the end of step 2, the result variable will have the required result (number that appears only once). Therefore, we return this as our 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

In order to perform XOR operation on all elements, we will have to iterate through every element in nums array. Therefore the time complexity of this solution is O(n).

Space Complexity

The space complexity of this algorithm is O(1) as we are not using any extra space.

That brings us to the end of this article. We sincerely appreciate the time you have taken to read through it. If there are 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.