0136-single-number-easy.md

description
Author: @wkw, @vigneshshiv, @radojicic23 | https://leetcode.com/problems/single-number/

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

:::info 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$.

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

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

// 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\ast 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\ast 7-10=4$.

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;
    }
};

/**
 * @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;
};

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