How can I find missing numbers in a list without using LINQ?

Question

public static class MyExtensions
{
    /// <summary>
    /// Finds the missing numbers in a list.
    /// </summary>
    /// <param name="list">List of numbers</param>
    /// <returns>Missing numbers</returns>
    public static IEnumerable<int> FindMissing(this List<int> list)
    {
        // Sorting the list
        list.Sort();

        // First number of the list
        var firstNumber = list.First();

        // Last number of the list
        var lastNumber = list.Last();

        // Range that contains all numbers in the interval
        // [ firstNumber, lastNumber ]
        var range = Enumerable.Range(firstNumber, lastNumber - firstNumber);

        // Getting the set difference
        var missingNumbers = range.Except(list);

        return missingNumbers;
    }
}

Now you can call the extension method in the following way:

class Program
{
    static void Main(string[] args)
    {
        // List of numbers
        List<int> daysOfMonth =
        new List<int>() { 6, 2, 4, 1, 9, 7, 3, 10, 15, 19, 11, 18, 13, 22, 24, 20, 27, 31, 25, 28 };

        Console.Write("\nList of days: ");

        foreach(var num in daysOfMonth)
        {
            Console.Write("{0} ", num);
        }

        Console.Write("\n\nMissing days are: ");

        // Calling the Extension Method in the List of type int 
        foreach(var number in daysOfMonth.FindMissing())
        {
            Console.Write("{0} ", number);
        }
    }
}

I am using 2.0 frame work so instead of var what should i use — Vivekh, Sep 05 '11 at 09:32
If you're using the 2.0 framework then you won't have extension methods either. — Tim, Sep 05 '11 at 09:34
do a `simple for(int i=1;i<31;i++) { if(daysOfMonth.Contains(i)) { .. OK ... }}` — Steve B, Sep 05 '11 at 09:35
You can [use Linq with the 2.0 framework if you jump through some hoops](http://stackoverflow.com/questions/2138/linq-on-the-net-2-0-runtime). The syntax sucks, since extension method syntax is missing, but at least you won't have to code it from scratch. Or [as one of the answers on that page suggests, use LinqBridge](http://stackoverflow.com/questions/2138/linq-on-the-net-2-0-runtime/394595#394595). — Merlyn Morgan-Graham, Sep 05 '11 at 09:39
Steve B has the right answer, I believe, if OP is constrained to the 2.0 framework. Use the `List` Contains method and a for loop. — Tim, Sep 05 '11 at 09:40
Extension methods are C# compiler trick and nothing to do with .NET Fx. So basically if you use C# 3.0 compiler and target .NET 2.0 you can still use extension methods — Ankur, Sep 05 '11 at 09:43

score 2 · Accepted Answer · edited Sep 05 '11 at 09:40

2

public static IEnumerable<int> FindMissing(List<int> list)
{
    if (list.Count < 3) yield break;
    List<int> listClone = new List<int>(list); //do not modify the original list
    listClone.Sort();
    for (int n = listClone[i] ; n < listClone[listClone.Count - 1]; n++)
        if (!listClone.Contains(n))
            yield return n;
}

And of course this may be optimized not to traverse the entire listClone every time

edited Sep 05 '11 at 09:40

dtb

213,145
36
401
431

answered Sep 05 '11 at 09:36

Snowbear

16,924
3
43
67

OP said he's on the 2.0 Framework - this looks like an extension method, which won't for him (3.0+ for extensions). – Tim Sep 05 '11 at 09:39
I said that i am using c# 2.0 – Vivekh Sep 05 '11 at 09:39
I've made some tiny adjustments so it should work with C# 2.0 – dtb Sep 05 '11 at 09:41
@Vivekh, you should state the requirements while entering the qquestion. I've answered it before you've added the requirement. You may disregard my answer if you need .Net framework 2.0. – Snowbear Sep 05 '11 at 09:42
@dtb, `yield return` and `yield break` were part of .Net framework 2.0 – Snowbear Sep 05 '11 at 09:45

score 2 · Answer 2 · answered Sep 05 '11 at 09:38

Actually, your own code is not doing what it is expected to do.

The method documentation pretends that FindMissing will find what numbers are missing from Min..Max range of a list. Instead, the method actually finds the missing numbers between the first and the last value in a list. In other words, in a given example, I expect the search to be done from 1 to 31. Instead, the method will search from 6 to 28.

Now, if you need to transform this into a non-LINQ method, try it step by step :

The method uses list.First() and list.Last(). You can have both values by using indexes and list.Count.
The method uses Enumerable.Range. The behavior is easily reproduced with a for loop.
The method uses IEnumerable.Except(). You can find the missing values yourself by looping through the list.

The OP first sorts the list, so he doesn't check from 6 to 28 but from 1 to 31, BUT only because those values are present in the list - he still has that error. — Hans Keﬆing, Sep 05 '11 at 09:44

How can I find missing numbers in a list without using LINQ?

2 Answers2