Practice › Bit Manipulation
Two Non-Repeating Numbers
Medium · Bit Manipulation · Asked at Amazon, Microsoft, Google, Samsung
Every value appears exactly twice except two different values that appear once. Print those two values in increasing order, using O(1) extra space.
Input
First line: n. Second line: n space-separated integers.
Output
The two values, smaller first.
Constraints
- 2 ≤ n ≤ 10^5
- 0 ≤ a[i] ≤ 2^31 − 1
XOR of everything = x ^ y ≠ 0. Pick any set bit of it; split the numbers by that bit and XOR each group separately — one group gives x, the other y.
Example 1
Input
6 1 2 3 2 1 4
Output
3 4
Example 2
Input
2 2 1
Output
1 2
Hints
- XOR of all numbers cancels the pairs and leaves x ^ y, which is not 0 because x ≠ y.
- Pick a set bit of x ^ y (e.g. the lowest). x and y differ there, so splitting all numbers by that bit puts x and y in different groups; XOR each group.
Approach
xy = XOR of all. bit = xy & −xy isolates its lowest set bit. XOR together all numbers having that bit to get one of the singles; the other is xy ^ first. Pairs always land in the same group and cancel. Print the two values in increasing order.
Complexity: O(n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n);
long long xy = 0;
for (auto &x : a) cin >> x, xy ^= x;
long long bit = xy & -xy, x = 0;
for (long long v : a)
if (v & bit) x ^= v;
long long y = xy ^ x;
cout << min(x, y) << " " << max(x, y) << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
a = data[1 : 1 + data[0]]
xy = 0
for v in a:
xy ^= v
bit = xy & -xy
x = 0
for v in a:
if v & bit:
x ^= v
y = xy ^ x
print(min(x, y), max(x, y))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] a = new long[n];
long xy = 0;
for (int i = 0; i < n; i++) {
a[i] = sc.nextLong();
xy ^= a[i];
}
long bit = xy & -xy, x = 0;
for (long v : a) if ((v & bit) != 0) x ^= v;
long y = xy ^ x;
System.out.println(Math.min(x, y) + " " + Math.max(x, y));
}
}Solve Two Non-Repeating Numbers online · All practice problems