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 <vector>
2using namespace std;
3
4int singleNumber(vector<int>& nums) {
5 int ones = 0, twos = 0, common = 0;
6 for (int num : nums) {
7 twos |= ones & num;
8 ones ^= num;
9 common = ones & twos;
10 ones &= ~common;
11 twos &= ~common;
12 }
13 return ones;
14}
15
16int main() {
17 vector<int> nums = {0, 1, 0, 1, 0, 1, 99};
18 return singleNumber(nums);
19}The logic remains the same as in C; we use two variables to count occurrences of bits. The primary operation is to shift bits between 'ones' and 'twos' based on their appearance count, zeroing them out when doubled up simultaneously in these trackers.
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.
1import
A map data structure in Java counts the occurrence of each number. Once filled, the map is iterated over to find the number that appears only once. While straightforward, this approach uses extra space, making it less optimal for the stated constraints.