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.

Sort + Search

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 <iterator>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() 
{
    int n; cin >> n;
    vector<int> v(n-1);
    copy_n(istream_iterator<int>(cin), n-1, begin(v));
    sort(begin(v), end(v));
    auto missing = n;
    for (auto i=1; i<n; ++i)
    {
        if (i != v[i-1])
        {
            missing = i;
            break;
        }
    }
    cout << missing;
}

In Haskell:

1
2
3

import Data.List (sort)
findTheMissingValue (_:xs) = head [ i | (x, i) <- zip (sort xs) [1..], i /= x ]
main = interact $ show . findTheMissingValue . fmap read . words

Pros:

  • easy to extend to a more generic domain (e.g. if we have a baseline array, we can easily adapt this solution to locate the element missing in the second array)
  • with a small effort, can work with duplicates

Cons:

  • we pay sort - \( O(N \cdot logN) \)
  • requires modifying the array (what if not permitted?)

Variant: use binary search to locate the missing value, since the array is sorted.

Optimized sort + search

Since the domain is \( [1-N] \), we can actually sort in \( O(N) \) by applying Cycle sort (we can even sort with Counting sort or such, however those require some additional storage):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

int N;
cin >> N;
vector<int> v(N);
copy_n(std::istream_iterator<int>(cin), N - 1, begin(v));
auto i = 0;
while (i<N) 
{
    auto correct = v[i] - 1;
    if (v[i] < N && v[i] != v[correct]) 
    {
        swap(v[i], v[correct]);
    }
    else 
    {
        i++;
    }
}

for (auto i = 0; i<N; i++) 
{
    if (i != v[i] - 1) {
        std::cout << i + 1;
        return 0;
    }
}

cout << N;

Pros:

  • it’s linear (we have a linear number of swaps since we already know the final position of every element)
  • minimal number of element writes

Cons:

  • we do modify the array
  • if the domain changes, cycle sort might be inconvenient (in general, it’s quadratic)

Additional Storage

We could keep track of elements into a support storage (e.g. a flag array). This is just an example:

1
2
3
4
5

vector<bool> hits(n, false); // C++ addicted will disapprove this!
for (auto val : v)
    hits[val-1] = true;
    
cout << (distance(begin(hits), find(begin(hits), end(hits), false))+1);

Pros:

  • it’s linear
  • we do not modify the input array
  • easy to extend to a more generic domain and also to duplicates (e.g. turn the vector into a frequency array or map)

Cons:

  • we pay additional storage, but since the domain is relatively small, we can use constant storage:
1
2
3
4
5
6
7
8

int n, el;
array<bool, 1'000'000> hits;
for (auto i=0; i<n; ++i)
{
    cin >> el;
    hits[el-1] = true;
}
cout << (distance(begin(hits), find(begin(hits), end(hits), false))+1);

A possible space optimization consists in using a std::bitset that packs bits together (but things might get slower, it should be measured).

Mathematics

We can exploit the problem domain to the limit.

  • calculate the sum of all the numbers from \( 1 \) to \( N \). Call it \( expected \)
  • calculate the sum of input numbers. Call if \( sum \)
  • the missing value is just \( expected - sum \)

It’s interesting to note that the sum from \( 1 \) to \( N \) is the Gauss Formula:

\( \dfrac{n(n+1)}{2} \)

In C++:

1
2
3

auto sum = accumulate(begin(v), end(v), 0ull); // aka: reduce
auto expected = n*(n+1)/2;
cout << (expected - sum);

Pros:

  • efficient
  • no extra space
  • we do not modify the input array
  • the same idea (summation, not Gauss) can be reused to solve the same problem in more generic domains

Cons:

  • what if \( \dfrac{n(n+1)}{2} \) overflows?

The overflow problem is worth discussing in a bit more detail. In C++, signed integer overflow results in undefined behavior, whereas unsigned integer overflow is well-defined and wraps around modulo \(2^k\).

An interesting consequence is that we can safely use unsigned integers here if we don’t use Gauss: suppose we compute the expected sum from 0 to n incrementally (1 + 2 + 3 + ... + n) and then subtract the sum of the input elements. Both sums may overflow, but this does not affect the final result.

This is because unsigned arithmetic is performed modulo \(m\), and addition and subtraction are compatible with modular arithmetic:

1

(a + b) mod m = ((a mod m) + (b mod m)) mod m

and similarly for subtraction:

1

(a - b) mod m = ((a mod m) - (b mod m)) mod m

Therefore, even if the individual sums wrap around and no longer represent their mathematical values, their difference remains equal to the missing number modulo \(m\), which is exactly the result we are looking for.

A subtle but important detail is that this property does not necessarily hold if we compute the expected sum using Gauss’s formula we encountered above:  

1

n * (n + 1) / 2

  The reason is that modular arithmetic preserves addition and subtraction, but division is more delicate. In the incremental approach (1 + 2 + 3 + ... + n), every operation is an addition, so the result is exactly the mathematical sum reduced modulo \(m\).   With Gauss’s formula, however, the intermediate multiplication n * (n + 1) can overflow before the division by 2 takes place. Since:  

1

((a mod m) / 2) != (a / 2) mod m

  in general, the wrap-around introduced by the overflow is not guaranteed to be corrected by the subsequent division.   For example, with 32-bit unsigned integers (\(m = 2^{32}\)), the value of  

1

n * (n + 1)

  is computed modulo \(2^{32}\). Once overflow has occurred, information has been lost, and dividing the wrapped value by 2 may no longer produce the same result as computing the mathematical product first and dividing afterward.   Therefore, while the incremental summation is safe because it relies solely on addition and subtraction modulo \(2^k\), Gauss’s formula can yield an incorrect expected sum unless a wider integer type is used for the intermediate multiplication.

So, an operation is safe under fixed-width wraparound only if it’s congruence-preserving modulo \(2^k\). Addition and multiplication always are. Division is only safe when it’s exact (divides evenly) and performed before any wraparound has occurred (never after, and never in a way that requires forming an intermediate value that itself overflows).

Learning these things from an “easy” problem is not so bad, isn’t it?!

In Haskell there is no overflow, because the type Integer is unbounded (also known as bignum). This is similar in some other languages such as Python.

1
2
3

findTheMissingValue :: [Integer] -> Integer
findTheMissingValue (n:xs) = (n * (n + 1) `div` 2) - sum xs
main = interact $ show . findTheMissingValue . fmap read . words

Also, there is a C++ variation that performs a single linear scan and works for the same reason discussed above:  

1
2
3
4
5
6

auto total = 1ull;
for (auto i = 2ull; i <= n; ++i)
{
total = (total + i) - v[i - 2];
}
cout << total;

  The key observation is that this approach uses only additions and subtractions. When total is an unsigned integer type, all operations are performed modulo \(2^k\. Therefore, even if intermediate results overflow and wrap around, modular arithmetic guarantees that the final result remains correct.   In other words, the algorithm computes:  

1

(1 + 2 + ... + n) - (sum of all elements in v)

  entirely in modulo \(2^k\) arithmetic. Since addition and subtraction are compatible with modular arithmetic, any wrap-around affects both sides consistently, and the final difference is still the missing value.

XOR

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

It’s based on the XOR primitive’s main 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

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 sparse domains (a baseline array and one which misses exactly one element from that)

Cons:

  • tricky ;)

Marking array elements

Another - a bit hackish - solution to solve the problem consists in marking array elements as negative by using array elements as indexes.

For example:

1

5 1 3 2

The first pass of the algorithm marks as negative those numbers whose indexes are elements of the array (they are not missing elements):

  • 5 can’t lead to any numbers marked because it would go out of bounds
  • 1 leads to marking 5 as -5 (because 5 is at 1’s position that is 0)
  • 3 leads to marking 3 as -3 (because 3 is in the right position)
  • 2 leads to marking 1 as -1 (because 1 is at 2’s position that is 1)

So, after this first pass, the array will look like:

1

-5 -1 -3 2

The second part of the algorithm checks if any of the numbers is not negative. If any, the missing element is just the next index (because the domain starts from 1). In this case above, the missing element is 4 because 2 is positive and lies at index 3 (so the solution is the number 3+1).

The only exception is when, after the first pass, all the elements get negative. Here, the missing element is just N:

1

4 1 3 2

After the first pass:

1

-4 -1 -3 -2

The missing element is 5 (N=5).

Talk is cheap, show me the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

int n; cin >> n;
vector<int> v(n-1);
copy_n(istream_iterator<int>(cin), n-1, begin(v));

for (int i = 0; i < n; i++)
{
    int absVal = abs(v[i]);
    if (absVal - 1 < n)
    {
        v[absVal - 1] = -v[absVal - 1];
    }
}

for (int i = 0; i < n; i++)
{
    if (v[i] > 0) 
    {
        cout << (i + 1);
        return 0;
    }
}

cout << n;

Side note: we can restore the original array by turning negative elements positive.

Pros:

  • still linear
  • can’t overflow

Cons:

  • not easily generalizable
manifold  frequency-table  math 
We've worked on this challenge in these gyms: modena  padua  milan  barcelona  turin  bari  rome  polimi  lecce  brianza  latina 
comments powered by Disqus