# Find the Missing Value

See the original problem on HackerRank.

Given an unsorted array of $$n-1$$ elements, it is missing exactly one element from the sequence of $$1$$ to $$n$$. Find the missing element.

### Input Format

An integer $$n$$ followed by $$n-1$$ space separated numeric values.

### Constraints

$$1<n<10^6$$

### Output Format

The missing value.

## Solutions

This is an example of problems that we call manifold at Coding Gym, since they give us room to find several alternative solutions.

We sort the input array and we linearly scan the sequence to find the missing value. For example: In C++:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24  #include #include #include #include #include using namespace std; int main() { int n; cin >> n; vector v(n-1); copy_n(istream_iterator(cin), n-1, begin(v)); sort(begin(v), end(v)); auto missing = n; for (auto i=1; i

### XOR

The following solution is very similar to the previous one but it never overflows.

It’s based on XOR property:

• $$A \oplus B = C$$
• $$A \oplus C = B$$
• $$B \oplus C = A$$

That’s the idea:

• suppose $$A$$ is the result of XORing all the input elements
• suppose $$B$$ is the missing value
• the result of XORing $$A \oplus B$$ is $$C$$
• then $$C$$ is the result of XORing all the elements from 1 to N
• we can easily find $$B$$ as $$A \oplus C$$

Talk is cheap, let’s look at some code:

 1 2 3 4 5 6 7 8  auto xorVals = accumulate(begin(v), end(v), 0, bit_xor<>{}); // aka: reduce auto expected = 0; // naive approach, for an efficient method see, for instance, // here https://www.geeksforgeeks.org/calculate-xor-1-n/ for (auto i=1; i<=n; ++i) expected ^= i; cout << (expected ^ xorVals); 

In Haskell, but reducing with xor on a single list: the concatenation of the original list plus numbers from 1 to n.

 1 2 3 4 5  import Data.Bits (xor) findTheMissingValue :: [Integer] -> Integer findTheMissingValue (n:xs) = foldl xor 0 ([1..n] ++ xs) main = interact \$ show . findTheMissingValue . fmap read . words 

Pros:

• never overflows
• the same idea can be reused to solve the same problem in more generic domains

Cons:

• tricky ;)
We've worked on this challenge in these gyms: modena  padua  milan  barcelona  turin  bari  rome  polimi