Detect the missing number in a randomly-sorted array

Question

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<int, bool>();

        for (int i = min; i <= max; i++)
        {
            dictionary[i] = false;
        }

        foreach (int number in numbers)
        {
            dictionary[number] = true;
        }

        return dictionary.Keys.First(key => !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:

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

        // Eventually we could cache this if we use the results a lot
        for (int i = min; i <= max; i++)
        {
            expectedSum += i;
        }

        foreach (int number in numbers)
        {
            actualSum += number;
        }

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

        return missingNumber;
    }

Next, for completeness, here's the code I use to generate the random arrays in the first place:

/// <summary>
    /// Generate an array with all of the numbers except 1 between <paramref name="min"/> and <paramref name="max"/> in random order
    /// </summary>
    /// <param name="min">Smallest number in the array (inclusive)</param>
    /// <param name="max">Largest number in the array (inclusive)</param>
    /// <returns>Array</returns>
    /// <example>
    /// If min = 1 and max = 5, then we start with the array 1, 2, 3, 4, 5.
    /// 
    /// We then remove a random number (say, for example, 2), which leaves us with 1, 3, 4, 5.
    /// 
    /// We then shuffle the array by swapping random indices and return the result - e.g. 4, 1, 5, 3.
    /// </example>
    private static int[] GenerateRandomArray(int min, int max)
    {
        List<int> array = new List<int>();
        for (int i = min; i <= max; i++)
        {
            array.Add(i);
        }

        Random random = new Random();

        // Now we shuffle the array by swapping two random indices
        // The maximum number for the loop is somewhat arbitrary, but we want it to be at
        // least as large as array.Count so that we can make sure that the array's
        // thoroughly shuffled
        for (int i = 0; i < random.Next(array.Count * 3); i++)
        {
            int j = random.Next(array.Count);
            int k = random.Next(array.Count);

            // If j == k we're not actually doing a swap
            // so generate a new k until we get something other than j
            while (j == k)
            {
                k = random.Next(array.Count);
            }

            int temp = array[j];

            array[j] = array[k];

            array[k] = temp;
        }

        // Remove an item at a random index
        array.RemoveAt(random.Next(array.Count));

        return array.ToArray();
    }

Here's an example of the calls:

        int[] randomArray = GenerateRandomArray(1, 10);

        int missingNumber = MissingNumber(randomArray, 1, 10);

        // For verification purposes - it's easier to see the missing number if the array's sorted
        int[] sortedArray = randomArray.OrderBy(i => i).ToArray();

        int missingNumber2 = MissingNumber2(randomArray, 1, 10);
        Console.WriteLine("Missing number: " + missingNumber.ToString());

Answer 1

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;
}

Answer 2

A solution which does not overflow, is XORing all the numbers istead of adding them, and XORing the result with the expected accumulated XOR over the range.

It is worth noting that the expected value can be computed in constant time, since XOR over the range [0, N] is N, 1, N+1, or 0 depending on N%4.

Answer 3

You can bring this from two loops down to one:

int numbersIndex = 0;
for (int currentVal = min; currentVal < max; currentVal ++)
{
    actualSum += numbers[numbersIndex++];
    expectedSum += currentVal;
}

expectedSum += max;

It won't help your big-O runtime (the version you posted with \$O(2n)\$ runtime reduces down to \$O(n)\$, so by big-O my version is just as fast) but it will help your actual runtime.

Of course, this creates the problem of int overflow (as does your solution).

var array = new int[] { int.MaxValue - 2, int.MaxValue };
var missingNumber = MissingNumber(array, int.MaxValue - 2, int.MaxValue);
Console.WriteLine(missingNumber + " : " + (int.MaxValue - 1));

To fix that:

private static int MissingNumber(int[] numbers, int min, int max)
{
    int missing = 0;

    // Eventually we could cache this if we use the results a lot
    int numbersIndex = 0;
    for (int i = min; i < max; i++)
    {
        missing += i;
        missing -= numbers[numbersIndex++];
    }
    missing += max;

    return missing;
}

Simply subtract and add together. Then we solve all the problems (mostly). :)

We can still run into a problem of int overflow if the range is large enough, and the values are in the right order. Without using a long type it's difficult to solve that if we don't first order the array. (Which increases runtime obviously.)

Answer 4

Providing a working example for the answer @vnp describes. Similar to the accepted answer, but avoids overflow.

1) Find the expected XOR value of all numbers in range.
2) Find the actual XOR value of all numbers in the number array.
3) XOR the expected and actual to get missing number.

As @vnp mentioned, the expected value is found in constant time using the "mod 4 trick". Because the min could be something other than 1, an extra steps are needed to get the expected value only over the range indicated.

public static int FindMissingNumber(int[] numbers, int min, int max) {
    int expected1 = GetExpectedXor(min - 1);
    int expected2 = GetExpectedXor(max);
    int expected = expected2 ^ expected1;
    int actual = GetXor(numbers);

    int missingNumber = expected ^ actual;

    return missingNumber;
}

// Returns the expected value resulting from performing a bitwise XOR over all numbers from 1 to max (inclusive).
private static int GetExpectedXor(int max) {
    switch (max % 4) {
        case 0: return max;
        case 1: return 1;
        case 2: return max + 1;
        case 3: return 0;
        default: throw new Exception();
    }
}

private static int GetXor(int[] numbers) {
    int v = numbers[0];

    for (int i = 1; i < numbers.Length; i++) {
        v = v ^ numbers[i];
    }

    return v;
}

Answer 5

Nothing more for me to say about the code that has not been said

Other than check arguments

I ran the two below for time
The first is 1/5 faster
LINQ never seems to win a timing test

public static int MissingNumer1(int[] array, int min, int max)
{
    if (max < min)
        throw new ArgumentException("max < min");
    if (array.Length != (max - min))
        throw new ArgumentException("array.Length != (max - min)");
    if (array.Min() < 0)
        throw new ArgumentException("array.Min()");
    if (array.Length != new HashSet<int>(array).Count())
        throw new ArgumentException("array.Length != new HashSet<int>(array).Count()");
    int sumMinMax = (max + min) * (max - min + 1) / 2;
    foreach (int num in array)
        sumMinMax -= num;
    return sumMinMax; 
}
public static int MissingNumer2(int[] array, int min, int max)
{
    if (max < min)
        throw new ArgumentException("max < min");
    if (array.Length != (max - min))
        throw new ArgumentException("array.Length != (max - min)");
    if (array.Min() < 0)
        throw new ArgumentException("array.Min()");
    int sumMinMax = (max + min) * (max - min + 1) / 2;
    sumMinMax -= array.Sum();
    return sumMinMax;
}

Answer 6

Your own discussion of your code says it all.

for (int i = 0; i < random.Next(array.Count * 3); i++)
{
  ...
}

This does not ensure the loop running at least the size of the array, in fact it maybe not run at all. You should probably do something like this:

int stop = array.Count + random.Next(array.Count * 3);
for (int i = 0; i < stop; i++)
{
  ...
}

I think the xor concept can be narrowed down to the below using linq assuming the input is valid in the context:

int index = 0;
int missing = array.Aggregate(0, (n, xos) => xos ^ (min + index++) ^ n) ^ max;
Console.WriteLine(missing);

Answer 7

Similar question is from Amazon interview where a missing number from randomly sorted 250 numbers i.e. 1 to 250, say stored in an array N, is to be found

I think it's simple

S=0

S=S+125.5 -N[i] where i = 0 to 249, looping it over 249 numbers, the value of S in the end is the answer and this approach can be generalized