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
This C solution uses an array to simulate a hash map, where each index corresponds to a potential value of nums[i]. It maps numbers from -30000 to +30000 to indices 0 to 60000 to handle negative numbers.