0136 - Single Number (Easy)

Problem Link

https://leetcode.com/problems/single-number/

Problem Statement

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

You must implement a solution with a linear runtime complexity 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.

Approach 1: Bit Manipulation

Prerequisite

You should understand properties of XOR.

Let's have a quick review.

• If we take XOR of a number and a zero, the result will be that number, i.e. $a \oplus 0 = a$.
• If we take XOR of two same numbers, it will return 0, i.e. $a \oplus a = 0$.
• If we take XOR of multiple numbers, the order doesn't affect the result, i.e. $a \oplus b \oplus c = a \oplus c \oplus b$.

Therefore, if we take XOR of all numbers, what's left would be that single number as every element that appears twice would be cancelled out. For example, $nums = [4,1,2,1,2]$, we can reorder it like $[1,1,2,2,4]$, and we got $(1 \oplus 1) \oplus (2 \oplus 2) \oplus 4 = 4$.

C++

Written by @wingkwong

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (auto x : nums) ans ^= x;
        return ans;
    }
};

Python

Written by @wingkwong

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(lambda x, y: x ^ y, nums)

Java

Written by @vigneshshiv

// Time complexity: O(n), where n - # of elements in the array
// Space complexity: O(1)
class Solution {
    /**
     * Given a list of integers where all integers occur even times, expect one which occur odd times
     *
     * Solution - XOR of any two same numbers will always be 0, and XOR of any number with 0 is the number itself.
     */
    public int singleNumber(int[] nums) {
        int x = 0;
        for (int num : nums) {
            x ^= num;
        }
        return x;
    }
}

Approach 2: Math

$2 * sumOfSet - (SumOfNumbers) = answer$

For example, $nums = [4,1,2,1,2]$, $sumOfSet$ is $1 + 2 + 4 = 7$ and $sumOfNumbers$is $1 + 1 + 2 + 2 + 4 = 10$. Then the answer is $2 *7 - 10 = 4$.

C++

Written by @wingkwong

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        set<int> s;
        int sumOfSet = 0, sumOfNumbers = 0;
        for (auto x : nums) {
            if (!s.count(x)) {
                s.insert(x);
                sumOfSet += x;
            }
            sumOfNumbers += x;
        }
        return 2 * sumOfSet - sumOfNumbers;
    }
};

JavaScript

Written by @radojicic23

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    let hashSet = new Set();
    let sumOfSet = 0;
    let sumOfNums = 0;
    for (let num of nums) {
        if (!hashSet.has(num)) {
            hashSet.add(num);
            sumOfSet += num;
        }
        sumOfNums += num;
    }
    return 2 * sumOfSet - sumOfNums;
};

Python

Written by @radojicic23

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        hash_set = set()
        sum_of_nums = 0
        sum_of_set = 0
        for n in nums:
            if n not in hash_set:
                hash_set.add(n)
                sum_of_set += n
            sum_of_nums += n
        return 2 * sum_of_set - sum_of_nums