CareerCup

sum and sum of squares should give it.

@Anonymous: Good one dude

There is a very slick XOR-based solution. First, reduce this problem to the problem of finding two unique numbers in an array where every other number occurs exactly twice. Just append or prepend all the numbers in the range 1..N to your array. No need to do it in the code, just in your imagination.

To solve this new problem, you run through the whole array and XOR everything. Duplicates cancel out, so you end up with XOR of the two unique numbers.

Here is when things get slick. The tricky part is to notice that you have too much information. A XOR of two numbers does you little good by itself, but if you take just one set bit from it, things change dramatically. The easiest bit to take is the least significant one: x & -x. Note that this XOR is never zero (those numbers are different), so there must be at least one bit set.

Now what you know about this bit is that it is different in those two numbers (by the very definition of XOR). You also know that other numbers come in pairs, so if any of them has this bit set, its pair must also have this bit set, and if one has this bit cleared, the other one must too. This means that if you XOR all the numbers that have this bit set, duplicates cancel out, and whatever remains is the one of the unique numbers that has this bit set (the other one will be filtered out). Having one number and the XOR of both, the other one is calculated easily.

The code:

pair<int, int> findMissing(const vector<int> &numbers) {
	const int n = numbers.size() + 2;
	int xor2 = 0;
	for (auto i : numbers)
		xor2 ^= i;
	for (int i = 1; i <= n; ++i)
		xor2 ^= i;
	int low1 = xor2 & -xor2;
	int a = 0;
	for (auto i : numbers) {
		if (i & low1)
			a ^= i;
	}
	for (int i = 1; i <= n; ++i) {
		if (i & low1)
			a ^= i;
	}
	return make_pair(a, a ^ xor2);
}

#include <iostream>

using namespace std;

void findMissing (int a[], int n, int lost[]){
int j=0;
int k=0;
for(int i=1; i<n; i++){
if (i==a[j])
j++;
else
lost[k++]=i;
}
}

void main()
{
int a[5]={1,3,4,6,7};
int lost[2]={0};
findMissing(a,7,lost);
cout<<lost[0]<<":"<<lost[1]<<endl;
}

is that so simple? or I got the question wrong?

{
#include <iostream>

using namespace std;

void findMissing (int a[], int n, int lost[]){
int j=0;
int k=0;
for(int i=1; i<n; i++){
if (i==a[j])
j++;
else
lost[k++]=i;
}
}

void main()
{
int a[5]={1,3,4,6,7};
int lost[2]={0};
findMissing(a,7,lost);
cout<<lost[0]<<":"<<lost[1]<<endl;
}
}
is that so simple or I got the question wrong?

@Anonymous
Of course your assumption that numbers are sorted is a big plus to make it a simple problem. Do you think your solution would work if numbers are not sorted?

Say the Unknown numbers are x and y.
x + y = n(n+1)/2 - (sum of input array);
x * y = n!/(product of input array);

2 eqns 2 unknowns. Solve quadratic eqn to get x and y.

XOR, bit, XOR, XOR.

Take an array A of size n.

Mark A[x], if x is found in the given sequence. Now a second pass will give the missing numbers and complexity is O(n).

XOR for a single number missing...