Sponsored
Sponsored
This approach uses bit manipulation to solve the problem with constant space and linear runtime. The idea is to count the number of times each bit is set in the given numbers modulo 3 using two integers. This effectively filters out the bits that appear in numbers repeated thrice and leaves the bits of the unique number.
Time Complexity: O(n) - where n is the number of elements in the array.
Space Complexity: O(1) - as only a fixed amount of space is used regardless of the input size.
1#include <stdio.h>
2
3int singleNumber(int* nums, int numsSize) {
4 int ones = 0, twos = 0, common;
5 for (int i = 0; i < numsSize; i++) {
6 twos |= ones & nums[i];
7 ones ^= nums[i];
8 common = ones & twos;
9 ones &= ~common;
10 twos &= ~common;
11 }
12 return ones;
13}
14
15int main() {
16 int nums[] = {2, 2, 3, 2};
17 int size = sizeof(nums) / sizeof(nums[0]);
18 printf("%d\n", singleNumber(nums, size));
19 return 0;
20}In this code, we maintain two variables ones and twos to track the bits' appearances. When a bit appears the first time, it will be set in ones. If it appears the second time, it moves to twos while being removed from ones. When it appears the third time, it is cleared from both ones and twos using a common mask. This helps in removing all bits that occur thrice, hence leaving behind the unique element.
This approach involves using a data structure to count occurrences of each number. Although this uses linear time complexity, it requires additional memory to store frequencies, which violates the constant space constraint.
Time Complexity: O(n log n) - primarily due to the sorting step.
Space Complexity: O(1) - if in-place sort is assumed.
1function
Using an object as a dictionary to store number occurrences offers effective counting but does not meet the problem's constraints for extra space, making it less suited for large datasets where space is limited.