Expert.
Put your skills to the test.

Problem summary

An unordered stream contains every object number exactly twice, except two distinct numbers that occur once. Find the two singletons under a very small memory limit.

Constraints

2 ≤ N ≤ 1000000, even; object numbers have at most 18 decimal digits; total memory allowance is 512 KB.

Worked example

Official statement example.

10
14
7
21
9
14
17
17
7
19
9

19 21

Solution analysis

1. The XOR of the stream is a XOR b, because every repeated value cancels. A set bit in this XOR distinguishes the two singletons. The usual two-pass solution partitions values by that bit, but the stream cannot be reread or stored here.
2. Instead keep 60 XOR accumulators, one per possible bit. When reading a number, XOR it into every accumulator whose bit is set in that number. Also maintain the overall XOR. Once the stream ends, choose any set bit of the overall XOR. Its accumulator contains exactly the singleton having that bit set.
3. The other singleton is obtained by XOR with the overall XOR; sort the pair. In the sample, repeated numbers cancel and the two remaining numbers are 19 and 21. Sixty 64-bit accumulators use only 480 bytes.

Why it works

For a chosen bit each repeated number either enters its accumulator twice or never, so it cancels. At any set bit of a XOR b exactly one singleton enters, leaving precisely that number. The other is recovered by XOR. Because the singletons differ, at least one such bit exists.

Watch out. Do not require a second input pass.,18 decimal digits require 64-bit storage.,The two singletons are distinct, so their XOR is nonzero.

Uses C stdio and 60 fixed accumulators so no input-sized memory or second pass is required. The historical 512 KB limit includes implementation-dependent runtime overhead; the algorithmic storage is below 1 KB.

// Key idea: For a chosen bit each repeated number either enters its accumulator twice or never, so it
// cancels. At any set bit of a XOR b exactly one singleton enters, leaving precisely that number.
#include<cstdio>
#include<cstdint>
using namespace std;
int main(){
    int n;
    if(scanf("%d",&n)!=1){
        return 0;
    }
    unsigned long long bucket[60]={},total=0;
    for(int i=0;i<n;++i){
        unsigned long long value;
        if(scanf("%llu",&value)!=1){
            return 0;
        }
        total^=value;
        unsigned long long bits=value;
        for(int bit=0;bits!=0;++bit){
            if(bits&1ULL){
                bucket[bit]^=value;
            }
            bits>>=1;
        }
    }
    int bit=0;
    while(((total>>bit)&1ULL)==0){
        ++bit;
    }
    unsigned long long a=bucket[bit],b=total^a;
    if(a>b){
        unsigned long long temporary=a;
        a=b;
        b=temporary;
    }
    printf("%llu %llu\n",a,b);
}