/ #algorithms 

Missing Number Algorithm

Solution to finding the missing number problem in C#

Problem

Given a list of n-1 integers in the range of 1 to n. There are no duplicates in the list. One of the integers is missing in the list. Find it!

Check the complete project on my Github

Example

Input:

[1, 2, 4, 6, 3, 7, 8]

Output:

5

Given that

1 + 2 + 3 + ... + n = n*(n + 1)/2

It can be proved by mathematical induction.

Solution

namespace MissingNumber
{
    class Program
    {
        public static int FindMissing(int[] array, int n)
        {
            var total = n*(n+1)/2;

            for (int i = 0; i < n-1; i++)
            {
                total -= array[i];
            }

            return total;
        }
        static void Main(string[] args)
        {
            int[] array = { 1, 2, 4, 5, 6 };
            Console.Write(FindMissing(array, 5));
            Console.ReadLine();
        }
    }
}

Note: As stated above n*(n+1)/2 is the same as adding numbers from 1 to n. Knowing that let’s solve the problem for n = 5.

Input:

[1, 2, 4, 5, 6]

Expected Output:

3

n = 5

n*(n+1)/2 = 5*(5+1)/2 = 5*(6)/2 = 30/2 = 15
1 + 2 + 3 + 4 + 5 = 15
15 = 15

The algorithm continues by sustracting 15 and the first number in the array and using the result to do the same with the next number in the array up to n - 1.

n - 1 = 4 // We are going to iterate from 0 to 4 not including the 4.
array[0] = 1 | 15 - 1 = 14
array[1] = 2 | 14 - 2 = 12
array[2] = 4 | 12 - 4 = 8
array[3] = 5 | 12 - 5 = 3 // This is the missing number!

And that solves the problem. Hope that helps!

Author

Abraham Laria

Sr. Software Engineer at Pinnacle Entertainment Inc. Aspiring Solution Architect, interested in Team Management.