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.
Examples:
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 × 104Each element appears twice except one that appears only once.
Approach 1 (Brute-force Hash Map):
- Create an empty
hash mapto store counts of each element. - Loop through the
array, update the count for each element. - Loop again to find the element with count
1and return it.
Time Complexity:
Time Complexity = O(n) We traverse the array twice: once for counting and once for checking.
Space Complexity:
Space Complexity = O(n)
The hash map may store counts for up to n elements in the worst case.
Dry Run
Input: nums = [4, 2, 1, 0, 5]
Step 1: Initialize hash = {}
First loop (counting occurrences):
i = 0 → nums[0] = 4 → not in hash → hash = {4: 1}
i = 1 → nums[1] = 2 → not in hash → hash = {4: 1, 2: 1}
i = 2 → nums[2] = 1 → not in hash → hash = {4: 1, 2: 1, 1: 1}
i = 3 → nums[3] = 0 → not in hash → hash = {4: 1, 2: 1, 1: 1, 0: 1}
i = 4 → nums[4] = 5 → not in hash → hash = {4: 1, 2: 1, 1: 1, 0: 1, 5: 1}
After first loop: hash = {4: 1, 2: 1, 1: 1, 0: 1, 5: 1}
Second loop (finding element with count = 1):
i = 0 → nums[0] = 4 → hash[4] = 1 → return 4
Final return = 4
Output: 4
var singleNumber = function(nums) {
let hash = {};
for (let i = 0; i < nums.length; i++) {
if (!hash[nums[i]]) {
hash[nums[i]] = 1;
} else {
hash[nums[i]]++;
}
}
for (let i = 0; i < nums.length; i++) {
if (hash[nums[i]] === 1) {
return nums[i];
}
}
};
class Solution:
def singleNumber(self, nums):
hash = {}
for num in nums:
hash[num] = hash.get(num, 0) + 1
for num in nums:
if hash[num] == 1:
return num
import java.util.HashMap;
public class Solution {
public int singleNumber(int[] nums) {
HashMap hash = new HashMap<>();
for (int num : nums) {
hash.put(num, hash.getOrDefault(num, 0) + 1);
}
for (int num : nums) {
if (hash.get(num) == 1) {
return num;
}
}
return -1;
}
}
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
int singleNumber(vector& nums) {
unordered_map hash;
for (int num : nums) {
hash[num]++;
}
for (int num : nums) {
if (hash[num] == 1)
return num;
}
return -1;
}
};
#include <stdio.h>
int singleNumber(int* nums, int numsSize) {
for (int i = 0; i < numsSize; i++) {
int count = 0;
for (int j = 0; j < numsSize; j++) {
if (nums[j] == nums[i]) count++;
}
if (count == 1) return nums[i];
}
return -1;
}
using System;
using System.Collections.Generic;
public class Solution {
public int SingleNumber(int[] nums) {
Dictionary hash = new Dictionary();
for (int i = 0; i < nums.Length; i++) {
if (!hash.ContainsKey(nums[i])) {
hash[nums[i]] = 1;
} else {
hash[nums[i]]++;
}
}
for (int i = 0; i < nums.Length; i++) {
if (hash[nums[i]] == 1) {
return nums[i];
}
}
return -1;
}
} Approach 2 (Optimal using XOR):
XORof two same numbers is 0:a ^ a = 0.XORof a number with0is the number itself:a ^ 0 = a- So, if all elements occur twice except one, XOR-ing all gives that unique number.
Time Complexity:
Time Complexity = O(n) where n is the number of elements in the array.
Space Complexity:
Space Complexity = O(1) No extra space used.
Dry Run
Input: nums = [4, 2, 1, 0, 5]
Step 1: Initialize xor = 0
Loop through array:
i = 0 → xor = 0 ^ 4 = 4
i = 1 → xor = 4 ^ 2 = 6
i = 2 → xor = 6 ^ 1 = 7
i = 3 → xor = 7 ^ 0 = 7
i = 4 → xor = 7 ^ 5 = 2
Final xor = 2
Output: 2
var singleNumber = function(nums) {
let xor = 0;
for (let i = 0; i < nums.length; i++) {
xor = xor ^ nums[i];
}
return xor;
};
class Solution:
def singleNumber(self, nums):
xor = 0
for num in nums:
xor ^= num
return xor
public class Solution {
public int singleNumber(int[] nums) {
int xor = 0;
for (int num : nums) {
xor ^= num;
}
return xor;
}
}
class Solution {
public:
int singleNumber(vector& nums) {
int xorVal = 0;
for (int num : nums) {
xorVal ^= num;
}
return xorVal;
}
};
int singleNumber(int* nums, int numsSize) {
int xor = 0;
for (int i = 0; i < numsSize; i++) {
xor ^= nums[i];
}
return xor;
}
using System;
public class Solution {
public int SingleNumber(int[] nums) {
int xor = 0;
for (int i = 0; i < nums.Length; i++) {
xor = xor ^ nums[i];
}
return xor;
}
} 
