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 <vector>
2#include <iostream>
3
4std::vector<int> singleNumber(std::vector<int>& nums) {
5 int xorAll = 0;
6 for (int num : nums) {
7 xorAll ^= num;
8 }
9
10 int diffBit = xorAll & (-xorAll);
11 int x = 0, y = 0;
12 for (int num : nums) {
13 if (num & diffBit) {
14 x ^= num;
15 } else {
16 y ^= num;
17 }
18 }
19 return {x, y};
20}
21
22int main() {
23 std::vector<int> nums = {1, 2, 1, 3, 2, 5};
24 std::vector<int> result = singleNumber(nums);
25 std::cout << "Single numbers are: " << result[0] << ", " << result[1] << std::endl;
26 return 0;
27}The C++ code performs similar XOR operations but utilizes Standard Template Library (STL) features like vectors for easier management of dynamic arrays while maintaining constant space complexity in terms of auxiliary variables.
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.