Detect the missing number in a randomly-sorted array

I was reviewing for an interview and encountered the following question (and I'm paraphrasing):


Suppose you're given a shuffled array of numbers containing all of the numbers between a min and a max, inclusive, with one number missing. For example, for an array of size 5, you could have something like 2, 5, 4, 1 (where 3 is missing).


How do you determine which one is missing?

When I was posting, I did discover a similar post here (that OP actually settled on a similar preferred solution as I did, but I came up with mine independently), but I have several other solutions as well (as well as a slightly different implementation).

I thought of a few possible solutions: the first (which I think is actually a bad solution) would be to sort the list and then look for which one is missing.

A really bad solution would be to try every possible number between the min and max (does the list contain 1? Does the list contain 2? Does the list contain 3? Etc.).

There are two good solutions that I thought of. First (which I think is the inferior of the two) uses a hash table - essentially, I "check off" every number in the range as I see it in the array I got and then I look to see which one is still false. It's below:

private static int MissingNumber2(int[] numbers, int min, int max)
    {
        var dictionary = new Dictionary();

        for (int i = min; i  !dictionary[key]);
    }

The simplest solution I came up with is to sum the items in the range and then sum the items in the actual array; the difference between them is the number that's missing. Here's that code:

```
///
/// Find the missing number in a randomly-sorted array
///
/// Array of random numbers between and (inclusive) with one number missing
/// Minimum number (inclusive)
/// Maximum number (inclusive)
/// Missing number
private static int MissingNumber(int[] numbers, int min, int max)
{
int expectedSum = 0;
int actualSum = 0;

You don't need to calculate the expected sum in a loop since you can use the formula:

\$ S = (a_1 + a_n) * n / 2 \$

Also it makes sense to use LINQ to get the actual sum:

private static int MissingNumber(int[] numbers, int min, int max)
{
    int expectedSum = (min + max) * (numbers.Length + 1) / 2;
    int actualSum = numbers.Sum();

    // I do realize I could just return this directly but this is slightly more convenient for debugging
    int missingNumber = expectedSum - actualSum;

    return missingNumber;
}

StackExchange Code Review Q#150966, answer score: 26