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.
1#include <stdio.h>
2
3int singleNumber(int* nums, int numsSize) {
4 int result = 0;
5 for (int i = 0; i < numsSize; ++i) {
6 result ^= nums[i];
7 }
8 return result;
9}
10
11int main() {
12 int nums[] = {2, 2, 1};
13 int numsSize = sizeof(nums) / sizeof(nums[0]);
14 printf("%d\n", singleNumber(nums, numsSize)); // Output: 1
15 return 0;
16}The function singleNumber iterates over the array and continuously performs an XOR operation. By the end of the loop, all pairs will cancel out, leaving the single number as the result.
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 <iostream>
2#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.