Introduction
Discovering a missing number in an array might seem straightforward, but it's a common problem in computer science, often encountered in coding interviews and competitive programming. Essentially, the task is to find a number that is missing from a sequence of integers. This might appear simple, yet it involves understanding efficient algorithms to solve it without bruteforce searching.
In this article, we're going to explore two effective approaches to tackle this problem. First, we'll use hashing to keep track of numbers in the array. Then, we'll shift to a mathematical method, leveraging the sum of the first N natural numbers.
Approach 1 (Using Hashing)
Hashing is a technique to map data of any size to a fixed size. In the context of finding a missing number in an array, hashing is super handy. It allows us to keep track of all the numbers present in the array in a way that's easy to check what's missing.
Here's how it works: we create a 'hash table' or a 'hash map' where each number from the array is stored as a key. This makes it quick to see if a number is present or not. Now, if we know the array should contain numbers from 1 to N, we can simply go through these numbers and check if each one is in our hash table. The one that's missing, well, that's our missing number!
Let's look at some code examples to make this clearer.
Output
Missing number is 3
In each of these examples, we're doing essentially the same thing: using a hash table to keep track of which numbers appear in the array. Then, we check for the missing number by looking for the first number that doesn't appear in our hash table. Simple & effective!
Use Hashing When

Handling Duplicates or Multiple Missing Numbers: If the array might contain duplicates or you need to find more than one missing number, hashing is more flexible.

Avoiding Integer Overflow: For arrays with very large numbers or a large range of values, the summation method might lead to integer overflow. Hashing doesn't have this issue.
 Need for Speed with Sufficient Memory: Hashing can be faster for lookup operations if memory usage is not a primary concern.