Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. XOR of all numbers cancels the pairs and leaves x ^ y, which is not 0 because x ≠ y.
  2. 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