Sponsored
Sponsored
This approach leverages the properties of XOR bitwise operation. The XOR of a number with itself is 0, and the XOR of a number with 0 is the number itself. Thus, XORing all elements in the array results in getting the single number because all other numbers cancel themselves out.
Time Complexity: O(n) - We go through the array once.
Space Complexity: O(1) - We only use a single integer to store the result.
1function singleNumber(nums) {
2 let result = 0;
3 for (let num of nums) {
4 result ^= num;
5 }
6 return result;
7}
8
9const nums = [2, 2, 1];
10console.log(singleNumber(nums)); // Output: 1This JavaScript function iterates over the nums array, utilizing the XOR operation to eliminate duplicates, leaving behind the single number.
In this approach, we use a hash map (or dictionary) to count occurrences of each number. The single number will have a count of 1. This isn't the optimal solution in terms of extra space but is valid if space was not constrained.
Time Complexity: O(n) - We traverse the array twice (once for filling the map, once for checking the counts).
Space Complexity: O(n) - Extra space proportional to the input range.
1#include <unordered_map>
#include <vector>
int singleNumber(std::vector<int>& nums) {
std::unordered_map<int, int> countMap;
for (int num : nums) {
countMap[num]++;
}
for (const auto& pair : countMap) {
if (pair.second == 1) return pair.first;
}
return -1;
}
int main() {
std::vector<int> nums = {4, 1, 2, 1, 2};
std::cout << singleNumber(nums) << std::endl; // Output: 4
return 0;
}The C++ solution uses an unordered_map to count occurrences of each number. It returns the key with a count of one.