Missing number in an Integer sequence

04 Jun 2016

This is the basic question that is asked in many technical interview to test your problem solving skill and also your fluency in writing algorithm.

Problem Statement:

You are provided with a sequence of integer numbers in which a number is missing, write a program to find the missing number.

Cases to consider:

  1. The number can start from any number
  2. The numbers can be negative too.
  3. To solve the problem effectively with low time and space complexities

Solution:

Method 1:

This utilizes the basic mathematical formula that is used for calculating the sum of numbers in a sequence.

  1. Loop through the array of given numbers
  2. calculate the sum of numbers (totalOfGivenNumbers), find the minimum from the array(minNumber), find the maximum from the array(maxNumber)
  3. Expected sum of all numbers till the maxNumber : maxNumber * (maxNumber + 1) / 2
  4. If the minimum bound of this array is less than 1. Then, find the sum of all numbers below the array lower bound (minNumber) : minNumber * (minNumber + 1) /2
  5. Subtract the numbers arrived at (Step 3 - Step 4) this gives the expected sum of all numbers.
  6. Finally, the missing number can be found by Subtracting  expected sum of all numbers (Step 5) - sum of numbers in the given array ( calculated in step 2)

This method can overflow when the large integer numbers are present in array.

Time complexity : O(n)

public int FindMissingNumber(int[] numbers)
{
    int minNumber = int.MaxValue, maxNumber = int.MinValue;
    int totalOfGivenNumbers = 0;
    foreach (var n in numbers)
    {
        totalOfGivenNumbers -= n;
        minNumber = Math.Min(minNumber, n);
        maxNumber = Math.Max(maxNumber, n);
    }

    //Expected sum till the maxNumber in the List
    int expectedSum = (maxNumber * (maxNumber + 1)) / 2;

    //If the sequence doesn't start from 1. 
    //Then subract the sum of all numbers below the lower bound
    minNumber--;
    int excludeSumLessThanBounds = minNumber * (minNumber + 1) / 2;

    return totalOfGivenNumbers + (expectedSum - excludeSumLessThanBounds);
}

Method 2 :

This method utilizes the sorting of numbers in the array and then comparing the adjacent numbers in the array. If there is any discrepancy, then it returns the mid of two adjacent numbers in the array as the missing number.

Time Complexity : O(n log n)

/// <summary>
/// Sort the provided array and travese through to find the missing number
/// </summary>
/// <param name="numbers"></param>
/// <returns></returns>
public int FindMissingNumber1(int[] numbers)
{
    Array.Sort<int>(numbers);
    for (int i = 1; i < numbers.Length; i++)
        if (numbers[i] - numbers[i - 1] > 1)
            return (numbers[i] + numbers[i - 1]) / 2;
    return 0;
}

Sample driver program included below

using System;

namespace CodeSamples
{
    class MissingNumber
    {
        public int FindMissingNumber(int[] numbers)
        {
           
        }
        public int FindMissingNumber1(int[] numbers)
        {
        }
    }
    //Driver program
    class Program
    {
        static void Main(string[] args)
        {
            //Sequential numbers with no duplication
            int[] numbers = new int[] { -4, -6, -7, -3, -8, -2, -1, 0, 1, 2 };
            //int[] numbers = new int[] { -400, -399, -398, -396, -395, -394, -393, -392, -391, -390 };
            MissingNumber mn = new MissingNumber();
            Console.WriteLine("Method 1 : " + mn.FindMissingNumber(numbers));
            Console.WriteLine("Method 2 : " + mn.FindMissingNumber1(numbers));
        }
    }
}

You can find the related programming problem in Code Chef site.

If you have an alternative method kindly suggest.