C# Check for missing number in sequence

Question

I have an List<int> which contains 1,2,4,7,9 for example.

I have a range from 0 to 10.

Is there a way to determine what numbers are missing in that sequence?

I thought LINQ might provide an option but I can't see one

In the real world my List could contain 100,000 items so performance is key

Answer 1

var list = new List<int>(new[] { 1, 2, 4, 7, 9 });
var result = Enumerable.Range(0, 10).Except(list);

Answer 2

Turn the range you want to check into a HashSet:

public IEnumerable<int> FindMissing(IEnumerable<int> values)
{
  HashSet<int> myRange = new HashSet<int>(Enumerable.Range(0,10));
  myRange.ExceptWith(values);
  return myRange;
}

Will return the values that aren't in values.

Answer 3

Linqs Except method would be the most readable. Whether it performs adequately for you or not would be a matter for testing.

E.g.

range.Except(listOfValues);

Edit

Here's the program I used for my mini-benchmark, for others to plug away with:

static void Main()
{
    var a = Enumerable.Range(0, 1000000);
    var b = new List<int>();

    for (int i = 0; i < 1000000; i += 10)
    {
        b.Add(i);
    }

    Stopwatch sw = new Stopwatch();
    sw.Start();
    var c = a.Except(b).ToList();
    sw.Stop();
    Console.WriteLine("Milliseconds {0}", sw.ElapsedMilliseconds );
    sw.Reset();

    Console.ReadLine();
}

Answer 4

Create an array of num items

const int numItems = 1000;
bool found[numItems] = new bool[numItems];


List<int> list;

PopulateList(list);

list.ForEach( i => found[i] = true );

// now iterate found for the numbers found
for(int count = 0; i < numItems; ++numItems){
  Console.WriteList("Item {0} is {1}", count, found[count] ? "there" : "not there");
}

Answer 5

        List<int> selectedNumbers = new List<int>(){8, 5, 3, 12, 2};

        int firstNumber = selectedNumbers.OrderBy(i => i).First();
        int lastNumber = selectedNumbers.OrderBy(i => i).Last();

        List<int> allNumbers = Enumerable.Range(firstNumber, lastNumber - firstNumber + 1).ToList();

        List<int> missingNumbers = allNumbers.Except(selectedNumbers).ToList();

        foreach (int i in missingNumbers)
        {
            Response.Write(i);
        }

Answer 6

If the range is predictable I suggest the following solution:

public static void Main()
{
    //set up the expected range
    var expectedRange = Enumerable.Range(0, 10);

    //set up the current list
    var currentList = new List<int> {1, 2, 4, 7, 9};

    //get the missing items
    var missingItems = expectedRange.Except(currentList);       

    //print the missing items
    foreach (int missingItem in missingItems)
    {
        Console.WriteLine(missingItem);
    }

    Console.ReadLine();
}

Regards, y00daa

Answer 7

This does not use LINQ but it works in linear time.

I assume that input list is sorted.

This takes O(list.Count).

private static IEnumerable<int> get_miss(List<int> list,int length)
{
    var miss = new List<int>();
    int i =0;
    for ( i = 0; i < list.Count - 1; i++)
    {
        foreach (var item in 
                     Enumerable.Range(list[i] + 1, list[i + 1] - list[i] - 1))
        {
            yield return item;
        }

    }
    foreach (var item in Enumerable.Range(list[i]+1,length-list[i]))
    {
        yield return item;
    }
}

---

This should take O(n) where n is length of full range.

 static void Main()
    {
        List<int> identifiers = new List<int>() { 1, 2, 4, 7, 9 };

        Stopwatch sw = new Stopwatch();

        sw.Start();
        List<int> miss = GetMiss(identifiers,150000);
        sw.Stop();
        Console.WriteLine("{0}",sw.ElapsedMilliseconds);

    }
private static List<int> GetMiss(List<int> identifiers,int length)
{
    List<int> miss = new List<int>();

    int j = 0;

    for (int i = 0; i < length; i++)
    {
        if (i < identifiers[j])
            miss.Add(i);

        else if (i == identifiers[j])
            j++;

        if (j == identifiers.Count)
        {
            miss.AddRange(Enumerable.Range(i + 1, length - i));
            break;
        }
    }

    return miss;
}