Sponsored
Sponsored
The idea is to use the XOR operation to find two unique numbers that appear only once in the array. This can be achieved by:
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), constant space is used for variables non-dependent on input size.
1#include <stdio.h>
2
3void findSingleNumbers(int* nums, int size, int* result) {
4 int xorAll = 0;
5 for (int i = 0; i < size; i++) {
6 xorAll ^= nums[i];
7 }
8
9 int diffBit = xorAll & (-xorAll);
10 int x = 0, y = 0;
11 for (int i = 0; i < size; i++) {
12 if (nums[i] & diffBit) {
13 x ^= nums[i];
14 } else {
15 y ^= nums[i];
16 }
17 }
18 result[0] = x;
19 result[1] = y;
20}
21
22int main() {
23 int nums[] = {1, 2, 1, 3, 2, 5};
24 int result[2];
25 findSingleNumbers(nums, 6, result);
26 printf("Single numbers are: %d, %d\n", result[0], result[1]);
27 return 0;
28}This C program uses bitwise XOR to isolate the unique numbers. The key step is identifying a differing bit to partition the numbers, allowing separation of the unique numbers in linear time.
An alternative approach that utilizes hash maps to count occurrences of each element would typically find the unique numbers. Although this solution is more straightforward, it requires additional space and does not strictly meet the problem constraints of constant extra space.
Time Complexity: O(n), for passing through the array for counting.
Space Complexity: O(n), as space is allocated for counts of numbers.
1from collections import Counter
2
3def singleNumber(nums):
4 count
This Python solution leverages collections.Counter to track occurrences and quickly find numbers appearing only once. While simple, it utilizes additional space beyond the constraints of the problem for learning purposes.