stachenov
BAN USERThere 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);
}
Wow, no one ever heard of premature optimization? Performance obviously goes last. You don't have to worry about it until you have proven by measuring that there is a problem. And you only fix what's needed to be fixed.
Other qualities are tricky.
For example, correctness and maintainability. Maintainability is very important for virtually all code, except throwaway prototypes. Correctness, on the other hand, is very tricky. For some problems is essential, and therefore goes first. For some problems, some amount of incorrectness is tolerable. For yet another problems, correct solutions are either unreasonable (think NP-complete problems) or outright impossible (image recognition).
Ease of learning and use are closely related. But I'd put ease of use first because you only had to learn something once, but then you may have to use it for the rest of your life.
This is probably the best interview question I've ever heard.
With some template tricks, we can deduce the correct return type using another simple template, so the main template doesn't need any specialization:
template<typename T>
struct Aggregate {
typedef T type;
};
template<>
struct Aggregate<char> {
typedef string type;
};
template<typename T>
typename Aggregate<T>::type combine(T *first, size_t N) {
typename Aggregate<T>::type sum = typename Aggregate<T>::type();
for (T *p = first; p < first + N; ++p) {
sum += *p;
}
return sum;
}
One thing to note is that C++ is not exactly a superset of C. There are many subtle differences. For example, there is this thing called designated initializer in C99, that's basically a poor man's constructor for structs and a weird way to initialize arrays as well. There is no such thing in C++. There are even more subtle things, like
which compiles fine in C, resulting in a non-null-terminated string, but illegal in C++.
- stachenov October 20, 2016