0100 - 0199
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: 1Example 2:
Input: nums = [4,1,2,1,2]
Output: 4Example 3:
Input: nums = [1]
Output: 1Constraints:
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. .
- If we take XOR of two same numbers, it will return 0, i.e. .
- If we take XOR of multiple numbers, the order doesn't affect the result, i.e. .
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, , we can reorder it like , and we got .
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
For example, , is and is . Then the answer is .
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