Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Approach 1 (Using Hashing)
2.1.
C
2.2.
C++
2.3.
Java
2.4.
Python
2.5.
Use Hashing When
3.
Approach 2 (Using Summation of First N Natural Numbers)
3.1.
C
3.2.
C++
3.3.
Java
3.4.
Python
3.5.
Opt for the Summation Approach When
4.
Frequently Asked Questions
4.1.
Why use hashing to find a missing number in an array?
4.2.
Is the summation approach always better than hashing?
4.3.
Can these methods find multiple missing numbers?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Missing Number in Array

Author Gaurav Gandhi
0 upvote
Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

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 brute-force searching. 

Missing Number in Array

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.

  • C
  • C++
  • Java
  • Python

C


#include <stdio.h>
#define MAX 100000

int main() {
int arr[] = {1, 2, 4, 5, 6};
int n = sizeof(arr)/sizeof(arr[0]);
int hash[MAX] = {0};

for (int i = 0; i < n; i++) {
hash[arr[i]] = 1;
}

for (int i = 1; i <= n; i++) {
if (hash[i] == 0) {
printf("Missing number is %d\n", i);
break;
}
}

return 0;
}

C++

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
int arr[] = {1, 2, 4, 6, 3, 7, 8};
int n = sizeof(arr)/sizeof(arr[0]);
unordered_set<int> hash;

for (int i = 0; i < n; i++) {
hash.insert(arr[i]);
}

for (int i = 1; i <= n + 1; i++) {
if (hash.find(i) == hash.end()) {
cout << "Missing number is " << i << endl;
break;
}
}

return 0;
}

Java

import java.util.HashSet;

public class Main {
public static void main(String[] args) {
int[] arr = {1, 2, 4, 6, 3, 7, 8};
int n = arr.length;
HashSet<Integer> hash = new HashSet<Integer>();

for (int i = 0; i < n; i++) {
hash.add(arr[i]);
}

for (int i = 1; i <= n + 1; i++) {
if (!hash.contains(i)) {
System.out.println("Missing number is " + i);
break;
}
}
}
}

Python

def find_missing(arr):
hash_set = set(arr)
n = len(arr) + 1

for number in range(1, n+1):
if number not in hash_set:
return number

arr = [1, 2, 4, 6, 3, 7, 8]
missing_number = find_missing(arr)
print(f"Missing number is {missing_number}")

 

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.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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
  • C++
  • Java
  • Python

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;
}

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;
}

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);
}
}

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}")

 

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 DSADBMSCompetitive ProgrammingPythonJavaJavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure and AlgorithmsCompetitive ProgrammingOperating SystemsComputer Networks, DBMSSystem Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.

Previous article
Max XOR of Two Numbers in an Array
Next article
Sum of middle elements of two sorted arrays
Live masterclass