Approach 2 (Using Summation of First N Natural Numbers)
Another smart way to find a missing number in an array involves a bit of math. Remember the formula for the sum of the first N natural numbers? It's N*(N+1)/2. We can use this to our advantage. If we sum up all numbers in the array & subtract it from the sum of the first N natural numbers, the result is our missing number!
This approach is great because it's straightforward & doesn't need extra space like hashing does. Here's the step-by-step:
-
Calculate the sum of the first N natural numbers using the formula.
-
Add up all the numbers in the array.
-
Subtract the array sum from the natural numbers sum.
-
The difference is the missing number!
Now, let's dive into the code examples to see how this plays out in different programming languages.
C
#include <stdio.h>
int main() {
int arr[] = {1, 2, 4, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
int total = (n + 1) * (n + 2) / 2;
for (int i = 0; i < n; i++) {
total -= arr[i];
}
printf("Missing number is %d\n", total);
return 0;
}

You can also try this code with Online C Compiler
Run Code
C++
#include <iostream>
using namespace std;
int main() {
int arr[] = {1, 2, 4, 6, 3, 7, 8};
int n = sizeof(arr) / sizeof(arr[0]);
int total = (n + 1) * (n + 2) / 2;
for (int i = 0; i < n; i++) {
total -= arr[i];
}
cout << "Missing number is " << total << endl;
return 0;
}

You can also try this code with Online C++ Compiler
Run Code
Java
public class Main {
public static void main(String[] args) {
int[] arr = {1, 2, 4, 6, 3, 7, 8};
int n = arr.length;
int total = (n + 1) * (n + 2) / 2;
for (int i : arr) {
total -= i;
}
System.out.println("Missing number is " + total);
}
}

You can also try this code with Online Java Compiler
Run Code
Python
def find_missing(arr):
n = len(arr)
total = (n + 1) * (n + 2) // 2
sum_arr = sum(arr)
return total - sum_arr
arr = [1, 2, 4, 6, 3, 7, 8]
missing_number = find_missing(arr)
print(f"Missing number is {missing_number}")

You can also try this code with Online Python Compiler
Run Code
Output
Missing number is 5
In each example, we start by calculating the total sum expected if no number was missing. Then, we go through the array, subtracting each number from this total. What remains at the end is the missing number. This method is quick, efficient, and easy to understand.
Opt for the Summation Approach When
-
Dealing with a Single Missing Number: If you're certain there's only one missing number, the summation method is straightforward and efficient.
-
Limited Memory Resources: The summation approach doesn't require additional data structures, making it more memory-efficient.
-
Simple Implementation: When teaching or explaining the concept to beginners, the summation method is more intuitive and easier to grasp.
Frequently Asked Questions
Why use hashing to find a missing number in an array?
Hashing allows you to keep track of all elements in the array efficiently. It's useful because you can quickly check if a number is present or not, making it easier to spot the missing one.
Is the summation approach always better than hashing?
Not necessarily. The summation approach is simple and doesn't require extra space, which is great. But, it might not be ideal for very large numbers due to the risk of integer overflow. In such cases, hashing could be more reliable.
Can these methods find multiple missing numbers?
The approaches discussed are designed to find a single missing number. To find multiple missing numbers, you'd need to tweak the methods slightly. For instance, with hashing, you'd look for all numbers not present in the hash table.
Conclusion
In this article, we've learned two effective strategies to tackle the common problem of finding a missing number in an array. The first approach leverages hashing, creating a quick-reference system to spot which number is absent. The second method uses a mathematical formula to find the discrepancy between the expected sum of numbers and the actual sum of the array. Both have their merits, and understanding when to use each can be a valuable tool in your coding.
You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.