Leetcode 136. Single Number

Problem Explanation

In this problem, we are given an array containing integers where every element appears twice except for one. We need to find that single integer.

E.g. If the array is [2,2,1] the output will be 1. As 1 is the only number which appears once in the array.

The challenge is to solve this problem in linear time complexity (O(n)) and without using any extra memory.

Solution Explanation

We can solve this problem using Bit Manipulation where we do a bitwise XOR of all the elements. XOR of all elements gives us the odd occurring elements. The reason is that XOR operation returns 0 if we take XOR of two same numbers and it returns the same number if we take XOR of a number with 0.

Example:

For the array [2,2,1], we will do an XOR operation for all the numbers.

i.e. ans XOR= array[idx] where ans = 0, array = [2,2,1] and idx = index of array from 0 to 2.

Initially, ans is 0 so we take XOR with 2 (first element), we get 2 (0 ^ 2 = 2),
then we take XOR of the result with 2 (next element) which results in 0 (as XOR of same numbers gives 0),
and finally, XOR of 0 with 1 gives 1 (0 ^ 1 = 1).

So, 1 is the answer and it's indeed the only element that appears once in the array.

C++ Solution

1
2cpp
3class Solution {
4public:
5    int singleNumber(vector<int>& nums) {
6        int ans = 0;
7        // Iterate over each number and XOR it
8        for (int num : nums)
9            ans ^= num;
10        // Return the result
11        return ans;
12    }
13};

Java Solution

1
2java
3class Solution {
4    public int singleNumber(int[] nums) {
5        int ans = 0;
6        // Iterate over each number and XOR it
7        for(int i=0;i<nums.length;i++){
8            ans ^= nums[i];
9        }
10        // Return the result
11        return ans;
12    }
13}

Python Solution

1
2python
3class Solution:
4    def singleNumber(self, nums):
5        ans = 0
6        # Iterate over each number and XOR it
7        for num in nums:
8            ans ^= num
9        # Return the result
10        return ans

JavaScript Solution

1
2javascript
3var singleNumber = function(nums) {
4    let ans = 0;
5    // Iterate over each number and XOR it
6    for(let i = 0;i<nums.length;i++){
7        ans ^= nums[i];
8    }
9    // Return the result
10    return ans;
11};

C# Solution

1
2csharp
3public class Solution {
4    public int SingleNumber(int[] nums) {
5        int ans = 0;
6        // Iterate over each number and XOR it
7        for(int i=0;i<nums.Length;i++){
8            ans ^= nums[i];
9        }
10        // Return the result
11        return ans;
12    }
13}

In each language, we iterate through all elements in the array and take XOR operation of previous result with the current element. Finally, we return the result which gives us the only single occurring element.## Ruby Solution

1
2ruby
3def single_number(nums)
4  ans = 0
5  # Iterate over each number and XOR it
6  nums.each do |num|
7    ans ^= num
8  end
9  # Return the result
10  return ans
11end

In Ruby, the method each is used for arrays to loop or iterate through each element. Using the ^ operator allows us to perform XOR operation, which effectively handles the task. Finally, we return the result.

Swift Solution

1
2swift
3func singleNumber(_ nums: [Int]) -> Int {
4    var ans = 0
5    // Iterate over each number and XOR it
6    for num in nums {
7        ans ^= num
8    }
9    // Return the result
10    return ans
11}

Swift also uses XOR operator and follows a similar structure. The function singleNumber uses a for-in loop to iterate through the array nums and applies XOR operation. The ans is updated with each iteration and the final outcome is returned.

It's worth noting that all these solutions across different programming languages follow the same conceptual procedures to solve the problem, and the key difference lies in the programming language syntax and existing libraries. The time complexity of all these solutions is O(n) which meets the requirement of the problem and thanks to XOR operation, no extra memory is needed to store any intermediate results, thereby satisfying the problem constraints.