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.
OR
Given an array of integers where every element appears exactly twice except for one element which appears only once, find that unique element.
Follow-up:
Given an array of integers where every element occurs an even number of times except one element which occurs an odd number of times, find that element.
classSolution {
publicintsingleNumber(int[] nums) {
HashSet<Integer> set =new HashSet<Integer> ();
for (int n: nums) {
if (!set.add(n)) {
set.remove(n);
}
}
Iterator<Integer> it = set.iterator();
return it.next();
}
}
1
2
3
4
5
6
7
8
9
10
11
classSolution:
defsingleNumber(self, nums: List[int]) -> int:
num_set = set()
for n in nums:
if n notin num_set:
num_set.add(n)
else:
num_set.remove(n)
# Since there's only one element left, we can return itreturn num_set.pop()
classSolution {
publicintsingleNumber(int[] nums) {
// Sort the array Arrays.sort(nums);
int n = nums.length;
for(int i=0; i < n - 1; i = i + 2) {
// compare num[i] with nums[i+1]// If nums[i] not equal to nums[i+1]// nums[i] is the number which occured only onceif(nums[i]!= nums[i+1]) {
return nums[i];
}
}
// As i = n-1 and no element left to compare, so this is the single number return nums[n-1];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolution:
defsingleNumber(self, nums: List[int]) -> int:
# Sort the array nums.sort()
n = len(nums)
# Iterate through the sorted array in steps of 2for i in range(0, n -1, 2):
# Compare nums[i] with nums[i + 1]# If they are not equal, nums[i] is the single numberif nums[i] != nums[i +1]:
return nums[i]
# If no mismatch found in pairs, the last element is the single numberreturn nums[n -1]
The key to solve this problem is bit manipulation. XOR will return 1 only on two different bits. So if two numbers are the same, XOR will return 0. Finally only one number left.
If every element occurs an even number of times except one (which occurs an odd number of times), XOR-ing all elements will leave the odd-occurring element. This is because all even-count elements cancel out, leaving only the one with odd frequency.
classSolution {
publicintsingleNumber(int[] nums) {
int ans = 0;
for (int num: nums) {
ans = ans ^ num;
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
classSolution:
defsingleNumber(self, nums: List[int]) -> int:
# Initialize ans as 0 ans =0# Iterate through each number in the arrayfor num in nums:
# XOR the current number with ans ans = ans ^ num
# Return the resultreturn ans