Log inSign up
mediumGeeksforGeeksNot Started

Find Two Non-Repeating Elements

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Bit Manipulation
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an integer array nums where every element appears exactly twice except for two unique elements which appear exactly once, find the two non-repeating elements.

Return the two numbers in ascending order (or as a pair/array) in linear time O(n) using constant auxiliary space O(1).

Example 1 · Example 1: Standard Array:

Input: nums = [1, 2, 3, 2, 1, 4]
Output: [3, 4]
Explanation: 1 and 2 appear twice. 3 and 4 appear once. Result is [3, 4].

Example 2 · Example 2: Negative and Positive:

Input: nums = [2, 1, 3, 2]
Output: [1, 3]
Explanation: 2 appears twice. 1 and 3 appear once.

Constraints:

  • 2 <= nums.length <= 105
  • nums.length is even
  • -109 <= nums[i] <= 109

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Deconstruct composite XOR sums into two distinct components.
  • Partition arbitrary arrays into independent bit-parity buckets.
  • Achieve optimal O(n) time and O(1) space without data mutation.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • All numbers appear twice except two unique numbers.
  • Find the two unique numbers in O(n) time and O(1) space.
  • Symmetric cancellation patterns.

Algorithmic Decision Tree:

  • Compute xorSum of all elements.
  • Find differentiating bit diffBit = xorSum & (-xorSum).
  • Maintain two XOR accumulators num1 and num2 separated by (num & diffBit).

Connected Patterns:

Single NumberSingle Number IISingle Number III

1. Hash Map Frequency Counting

Intuition

Populate frequency map. Loop through map keys and append values with count == 1 to the result array.

When to apply: Simplicity when extra memory is allowed.

Algorithm

  1. Step 1: Build frequency map of all elements.
  2. Step 2: Filter elements with frequency == 1.
  3. Step 3: Sort result array and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4#include <algorithm>
5
6using namespace std;
7
8vector<int> findTwoNonRepeatingBrute(const vector<int>& nums) {
9 unordered_map<int, int> freq;
10 for (int x : nums) freq[x]++;
11 vector<int> res;
12 for (auto& p : freq) {
13 if (p.second == 1) res.push_back(p.first);
14 }
15 sort(res.begin(), res.end());
16 return res;
17}
18
19int main() {
20 vector<int> nums = {1, 2, 3, 2, 1, 4};
21 auto res = findTwoNonRepeatingBrute(nums);
22 cout << "Brute: " << res[0] << ", " << res[1] << endl; // 3, 4
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(n)

2. Sorting and Scan

Intuition

Sort array in ascending order. Iterate index i through the array: if i + 1 < n and nums[i] == nums[i + 1], skip ahead i += 2. Otherwise, nums[i] is a single element; advance i++.

When to apply: When O(1) space is required but bit manipulation is not used.

Algorithm

  1. Step 1: Sort nums.
  2. Step 2: Loop i = 0 to n - 1.
  3. Step 3: If i + 1 < n and nums[i] == nums[i + 1], i++.
  4. Step 4: Else push nums[i] to result.
  5. Step 5: Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7vector<int> findTwoNonRepeatingSort(vector<int> nums) {
8 sort(nums.begin(), nums.end());
9 vector<int> res;
10 int i = 0;
11 while (i < (int)nums.size()) {
12 if (i + 1 < (int)nums.size() && nums[i] == nums[i + 1]) {
13 i += 2;
14 } else {
15 res.push_back(nums[i]);
16 i++;
17 }
18 }
19 return res;
20}
21
22int main() {
23 vector<int> nums = {1, 2, 3, 2, 1, 4};
24 auto res = findTwoNonRepeatingSort(nums);
25 cout << "Sort: " << res[0] << ", " << res[1] << endl; // 3, 4
26 return 0;
27}

Time & Space Complexity

  • Time complexity: O(n log n)
  • Space complexity: O(1) auxiliary space

3. Bitwise XOR Partitioning

Intuition

Compute xorSum of all elements. Isolate the lowest differentiating bit diffBit = xorSum & (-xorSum). In a second pass, XOR elements where (num & diffBit) != 0 into a, and elements where (num & diffBit) == 0 into b. Return [min(a, b), max(a, b)].

When to apply: Optimal canonical solution: linear O(n) time and strict O(1) space.

Algorithm

  1. Step 1: Compute xorSum = nums[0] ^ nums[1] ^ ... ^ nums[n - 1].
  2. Step 2: Isolate differentiating bit: diffBit = xorSum & (-xorSum).
  3. Step 3: Initialize num1 = 0, num2 = 0.
  4. Step 4: For each num: if (num & diffBit) != 0: num1 ^= num; else: num2 ^= num.
  5. Step 5: Return [min(num1, num2), max(num1, num2)].

XOR Partitioning Trace: [1, 2, 3, 2, 1, 4]

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Compute cumulative XOR of all elements: 1^2^3^2^1^4 = 3^4 = 7 (binary 111)
Visual state
Values and pointers at this exact step
pointers
S
111
0
↑ 3 ^ 4
Check / comparison
xorSum = 7
Decision / next transition
Set bits indicate differing positions between 3 and 4.
Why this step matters

Step 1: Compute cumulative XOR of all elements: 12^32^14 = 34 = 7 (binary 111).

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 vector<int> singleNumber(vector<int>& nums) {
10 long long xorSum = 0;
11 for (int x : nums) xorSum ^= x;
12
13 long long diffBit = xorSum & (-xorSum);
14 int a = 0, b = 0;
15 for (int x : nums) {
16 if ((x & diffBit) != 0) {
17 a ^= x;
18 } else {
19 b ^= x;
20 }
21 }
22 if (a > b) swap(a, b);
23 return {a, b};
24 }
25};
26
27int main() {
28 Solution sol;
29 vector<int> nums = {1, 2, 3, 2, 1, 4};
30 auto res = sol.singleNumber(nums);
31 cout << "Optimal: " << res[0] << ", " << res[1] << endl; // 3, 4
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Hash Map FrequencyO(n)O(n)Store frequencies in a hash map, then collect keys with frequency equal to 1.Hash map memory allocation.
2.Better — SortingO(n log n)O(1)Sort the array. Linearly scan comparing nums[i] with nums[i + 1]. Skip pairs.Sorting comparison.
3.Optimal — XOR PartitioningOptimalO(n)O(1)Two linear passes: first compute xorSum = a ^ b, then partition numbers by diffBit.Two linear scans.

Common Pitfalls & Crucial Edge Cases

Using a Hash Map when O(1) space is required

While a hash map solves it in O(n) time, it takes O(n) auxiliary space and fails the interview constraint.

Signed integer overflow on `diff & -diff`

If diff = INT_MIN, -diff overflows a 32-bit signed int in C++. Cast diff to unsigned int.

Not sorting the result pair

Forgetting to return in ascending order if required by the judge.

Crucial Edge Cases to Validate:

  • Smallest array size (n = 2) — Both elements are unique; XOR partition works directly.
  • Negative numbers — Negative numbers in two's complement can cause signed integer overflow on diff & -diff if diff = INT_MIN. Use unsigned integer casting (diff & -(unsigned)diff).
  • x and y differ only at the highest bit — Mask cleanly isolates that bit.
  • Arbitrary ordering requirement — Some platforms require the returned pair to be sorted [min(x, y), max(x, y)].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the insight clearly: XOR gives x ^ y, and any set bit in x ^ y is a discriminator where x has 1 and y has 0.
  2. Mention that this is the generalization of 'Single Number' to two unique elements.
  3. Highlight the O(1) auxiliary space advantage over sorting or hash sets.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.If all elements in an array appear twice except two distinct numbers x and y, what does XORing all elements produce?

2.How do you separate the numbers into two groups such that x and y fall into different groups?

3.What is the time and space complexity of this partitioning approach?

Back to DSA Sheet