Find Two Missing Numbers in O(n)

Given an array of n unique integers where each element in the array is in range [1, n]. The array is not necessarily sorted and has all distinct elements. The task is to find missing numbers if there is any.

Input  : {10, 5, 8, 1}
Output : 2, 3, 4, 6, 7, 9

Input : {3, 2, 4}
Output : 1 

Input : arr[] = {1, 2}
Output :

Algorithm: As array is not sorted so we first add all the items into dictionary (because reading is index based and quite fast).

Step1: Loop over the array and add all the items to our dictionary. Dictionary will have array items as KEY and if item is present in array then Value would be TRUE else FALSE.

Step2: Find the greatest item of the array.

Step3: Loop from 1 to the max item of the array

Step4. For each iteration of the loop, check whether this number is present in our Dictionary. if not present then print this number, otherwise skip.

class FindTwoMissingNumbers
    {
        static void Main(string[] args)
        {
            /// Input array
            int[] arr = { 10, 2, 8, 6, 5 };
 
            /// Temporary container. Array item will be our KEY and Value
            /// would be if TRUE that means item is not missing, FALSE 
            /// means item is missing so print this item.
            /// 
            Dictionary<int, bool> dict = new Dictionary<int, bool>();
 
            /// Add all the array items to this container. Array item 
            /// will be our KEY and value would be TRUE for all the items.
            for (int i = 0; i < arr.Length; ++i)
            {
                dict.Add(arr[i], true);
            }
 
            /// Loop from 1 to n (nth item of the array, i.e. max item of the array)
            int maxItem = arr.Max(x => x);
            for (int i = 1; i <= maxItem; ++i)
            {
                /// If a number is not present that means this is missing item
                /// so print it
                if (!dict.ContainsKey(i))
                {
                    Console.WriteLine(i);
                }
            }
 
            Console.ReadKey();
        }
    }

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s