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.
1function singleNumber(nums) {
2 let ones = 0, twos = 0;
3 for (let num of nums) {
4 twos |= ones & num;
5 ones ^= num;
6 let common = ones & twos;
7 ones &= ~common;
8 twos &= ~common;
9 }
10 return ones;
11}
12
13const nums = [0, 1, 0, 1, 0, 1, 99];
14console.log(singleNumber(nums));JavaScript utilizes a similar logical approach. The main operations—bitwise AND, OR, NOT, and XOR—enable fast calculations while retaining only the unique number in the end.
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.
1#include <vector>
#include <unordered_map>
using namespace std;
int singleNumber(vector<int>& nums) {
unordered_map<int, int> count;
for (int num : nums) {
count[num]++;
}
for (auto &pair : count) {
if (pair.second == 1) {
return pair.first;
}
}
return -1;
}
int main() {
vector<int> nums = {0, 1, 0, 1, 0, 1, 99};
return singleNumber(nums);
}In this approach, we use a hash map to count the frequency of each number, iterating through the array twice—first to populate the map and second to find the number appearing once. This requires additional space for the hash table.