How to find missing numbers in an Array?

One common way to find missing numbers in an array is to use a hash set to track the occurrence of elements, and then iterate through the range of possible values to check which ones are not in the set. Another way is to sort the array and then compare each element to its expected value to see which ones are missing.

Algorithm to find missing numbers in an array

Here is a simple algorithm to find missing numbers in an array using a hash set:

• Create an empty hash set.
• Iterate through the input array, adding each element to the set.
• Find the minimum and maximum values in the input array.
• Iterate through the range of possible values from the minimum to the maximum.
• For each value in the range, check if it is in the set.
• If a value is not in the set, add it to a list of missing numbers.
• Return the list of missing numbers.

Here is a similar algorithm to find missing numbers in an array using sorting:

• Sort the input array.
• Initialize a variable to store the expected value.
• Initialize a list to store missing numbers.
• Iterate through the sorted array.
• If the current value is not equal to the expected value, add the missing numbers between the expected value and the current value to the list.
• Increment the expected value by 1.
• Repeat steps 5-6 until all elements in the array have been processed.
• Return the list of missing numbers.

Here is an example to print the missing number in an array using a hash set:

def print_missing_number(arr): 
n = len(arr) 
s = set()
for i in range(n): 
s.add(arr[i]) 
for i in range(1, n+1): 
if i not in s: 
print(i) 
break

Here is an example to print the missing number in an array using sorting:

def print_missing_number(arr): 
n = len(arr) 
arr.sort()
expected_value = 1 
for i in range(n): 
if arr[i] != expected_value: 
print(expected_value) 
break
expected_value += 1

Using the Formula for Sum of First n Natural Numbers

Here's an example of how to find missing numbers in an array using the formula for the sum of the first n natural numbers:

def find_missing_number(arr): 
n = len(arr) 
expected_sum = n * (n + 1) // 2 
actual_sum = sum(arr) 
return expected_sum - actual_sum

This algorithm works by using the formula for the sum of the first “n” natural numbers, which is n * (n + 1) // 2. This formula gives the expected sum of the numbers from 1 to n. The algorithm then calculates the actual sum of the elements in the input array and subtracts it from the expected sum. The result is the missing number.

Using the sorting method to find the missing number in an array using C++

Here's an example of how to find the missing number in an array using the sorting method in C++:

Example:

// A sorting based C++ program to find missing
#include <bits/stdc++.h>
using namespace std;


void printMissing(int arr[], int n, int low,
				int high)
{
	// Sort the array
	sort(arr, arr + n);


	int* ptr = lower_bound(arr, arr + n, low);
	int index = ptr - arr;


	int i = index, x = low;
	while (i < n && x <= high) {


		if (arr[i] != x)
			cout << x << " ";


		// If x matches, move to next element in arr[]
		else
			i++;
		x++;
	}
	while (x <= high)
		cout << x++ << " ";
}
int main()
{
	int arr[] = { 1, 2, 4, 8, 9 };
	int n = sizeof(arr) / sizeof(arr[0]);
	int low = 1, high = 10;
	printMissing(arr, n, low, high);
	return 0;
}

Output:

3 5 6 7 10

This program uses the sorting method to find the missing number in an array.

Using XOR operator to find missing numbers in array

Here's an example of how to find missing numbers in an array using the XOR operator in C:

#include <stdio.h>
int find_missing_number(int arr[], int n) { 
int xor = 0; 
for (int i = 1; i<= n + 1; i++) { 
xor = xor ^ i;
 } 
for (int i = 0; i< n; i++) { 
xor = xor ^ arr[i];
 } 
return xor;
 } 
int main() { 
int arr[] = {1, 2, 4, 5, 6}; 
int n = sizeof(arr) / sizeof(arr[0]); 
printf("Missing number: %d\n", find_missing_number(arr, n)); 
return 0; 
} 

Output:

Missing number: 3

This program uses the XOR operator to find the missing number. The XOR operator has the property that A ^ A = 0. This means that if you XOR a value with itself, the result is 0. The find_missing_number function first XORs the numbers from 1 to n + 1 to get the expected XOR value. It then XORs the elements in the input array to get the actual XOR value. The difference between these two XOR values is the missing number. The main function demonstrates how to use the find_missing_number function to find the missing number in an example array.