Find the missing number
Given an array containing n distinct integers 0, 1, 2, ..., n. Write a method to find the one missing integer from the array
Example 1
Input: [1, 2, 0, 4]
Output: 3
Example 2
Input: [0, 2, 1, 4, 3, 6]
Output: 5
Approach
To solve the problem, we can use a hash to store all values and then check all items from 0 to n in the hash
- if an item doesn't exist in the hash, we found the
missingnumber - if all items are in the hash, return
-1because nothing missed
Code
public int MissingNumber(int[] array)
{
if (array == null || array.Length == 0)
{
return -1;
}
var cache = new HashSet<int>();
foreach (int item in array)
{
cache.Add(item);
}
for (int i = 0; i < array.Length + 1; i++)
{
if (cache.Contains(i) == false)
{
return i;
}
}
return -1;
}
Time Complexity: O(n)
Recent articles
Nice to read
