Algorithm
Problem Name: 136. Single Number
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 * 104-3 * 104 <= nums[i] <= 3 * 104- Each element in the array appears twice except for one element which appears only once.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int singleNumber(int* nums, int numsSize) {
int i, k = 0;
for (i = 0; i < numsSize; i ++) {
k = k ^ nums[i]; // a ^ a equals to 0; 0 ^ a equals to a
}
return k;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for(auto& x: nums) res ^= x;
return res;
}
};
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int singleNumber(int[] nums) {
int xor = nums[0];
for (int i = 1; i < nums.length; i++) {
xor ^= nums[i];
}
return xor;
}
}
Input
Output
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const singleNumber = function(nums) {
return nums.reduce((ac, e) => ac ^ e, 0)
};
Input
Output
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dic={}
for num in nums:
if not num in dic: dic[num]=1
else: dic.pop(num)
return list(dic.keys())[0]
Input
Output
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0136_SingleNumber
{
public int SingleNumber(int[] nums)
{
var a = 0;
foreach (var num in nums)
a ^= num;
return a;
}
}
}
Input
Output