Algorithm
Problem Name: 260. Single Number III
Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.
You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.
Example 1:
Input: nums = [1,2,1,3,2,5] Output: [3,5] Explanation: [5, 3] is also a valid answer.
Example 2:
Input: nums = [-1,0] Output: [-1,0]
Example 3:
Input: nums = [0,1] Output: [1,0]
Constraints:
2 <= nums.length <= 3 * 104-231 <= nums[i] <= 231 - 1- Each integer in
numswill appear twice, only two integers will appear once.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int* singleNumber(int* nums, int numsSize, int* returnSize) {
int i, k, a, b, *p;
k = 0;
for (i = 0; i < numsSize; i ++) {
k ^= nums[i];
}
k = k & ~(k - 1);
a = b = 0;
for (i = 0; i < numsSize; i ++) {
if (nums[i] & k) {
a ^= nums[i];
} else {
b ^= nums[i];
}
}
p = malloc(2 * sizeof(int));
p[0] = a;
p[1] = b;
*returnSize = 2;
return p;
}
Input
Output
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int[] singleNumber(int[] nums) {
int xorValue = Integer.highestOneBit(Arrays.stream(nums)
.boxed()
.reduce((a, b) -> a ^ b)
.orElse(0));
int[] result = new int[2];
for (int num : nums) {
if ((xorValue & num) == 0) {
result[0] ^= num;
} else {
result[1] ^= num;
}
}
return result;
}
}
Input
Output
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const singleNumber = function(nums) {
const hash = {};
nums.forEach((el, idx) => {
if (hash.hasOwnProperty(el)) {
hash[el] += 1;
delete hash[el];
} else {
hash[el] = 1;
}
});
return Object.keys(hash).map(el => +el);
};
Input
Output
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
return [n[0] for n in collections.Counter(nums).most_common()[-2:]]
Input
Output
#5 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0260_SingleNumberIII
{
public int[] SingleNumber(int[] nums)
{
int bitmask = 0;
foreach (int num in nums)
bitmask ^= num;
int diff = bitmask & (-bitmask);
int x = 0;
foreach (int num in nums)
if ((num & diff) != 0)
x ^= num;
return new int[] { x, bitmask ^ x };
}
}
}
Input
Output