Most Efficient Way to Find a Missing Number in an array
Have you wondered which is the most efficient way for a popular problem to find a missing Number? well in this post we are going to discuss this phenomenon in brief.
First, let’s discuss the problem statement:
Given an array of numbers from 1 to N (both inclusive). The size of the array is N-1. The numbers are randomly added to the array, there is one missing number in the array from 1 to N. What is the quickest way to find that missing number?
An approach using the XOR operator:
- We can use the XOR operation which is safer than summation because in programming languages if the given input is large it may overflow and may give wrong answers.
- Before going to the solution, know that
A xor A = 0. So if we XOR two identical numbers the value is 0. - Now, XORing [1..n] with the elements present in the array cancels the identical numbers. So in the end we will get the missing number.
How the XOR operator makes this algorithm efficient:
XOR has certain properties
- Assume a1 ⊕ a2 ⊕ a3 ⊕ . . . ⊕ an = a and a1 ⊕ a2 ⊕ a3 ⊕ . . . ⊕ an-1 = b
- Then a ⊕ b = an
- X ^ X = 0, i.e. Xor of the same values is zero.
Below is the implementation of the above idea:
#include <iostream>
using namespace std;
// Function to find the missing number
int findMissingNumbers(int arr[], int n)
{
int XOR = 0;
// XORing [1..n] with the elements present in the array
// cancels the identical numbers. So at the end we will
// get the missing number.
for (int i = 0; i < n - 1; i++) {
XOR ^= arr[i];
}
for (int i = 1; i < n + 1; i++) {
XOR ^= i;
}
return XOR;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 4, 5 };
int n = 5;
cout << findMissingNumbers(arr, n) << endl;
return 0;
}
/*code by flutterfly */
public class MissingNumberFinder {
// Function to find the missing number
public static int findMissingNumbers(int[] arr, int n) {
int XOR = 0;
// XORing [1..n] with the elements present in the array
// cancels the identical numbers. So at the end, we will
// get the missing number.
for (int i = 0; i < n - 1; i++) {
XOR ^= arr[i];
}
for (int i = 1; i < n + 1; i++) {
XOR ^= i;
}
return XOR;
}
// Driver code
public static void main(String[] args) {
int[] arr = {1, 2, 4, 5};
int n = 5;
System.out.println(findMissingNumbers(arr, n));
}
}
# code by flutterfly
# Function to find the missing number
def find_missing_numbers(arr, n):
XOR = 0
# XORing [1..n] with the elements present in the array
# cancels the identical numbers. So at the end, we will
# get the missing number.
for i in range(n - 1):
XOR ^= arr[i]
for i in range(1, n + 1):
XOR ^= i
return XOR
# Driver code
if __name__ == "__main__":
arr = [1, 2, 4, 5]
n = 5
print(find_missing_numbers(arr, n))
//code by flutterfly
using System;
public class MissingNumberFinder
{
// Function to find the missing number
public static int FindMissingNumbers(int[] arr, int n)
{
int XOR = 0;
// XORing [1..n] with the elements present in the array
// cancels the identical numbers. So at the end, we will
// get the missing number.
for (int i = 0; i < n - 1; i++)
{
XOR ^= arr[i];
}
for (int i = 1; i < n + 1; i++)
{
XOR ^= i;
}
return XOR;
}
// Driver code
public static void Main()
{
int[] arr = {1, 2, 4, 5};
int n = 5;
Console.WriteLine(FindMissingNumbers(arr, n));
}
}
// Function to find the missing number
function findMissingNumbers(arr, n) {
let XOR = 0;
// XORing [1..n] with the elements present in the array
// cancels the identical numbers. So at the end, we will
// get the missing number.
for (let i = 0; i < n - 1; i++) {
XOR ^= arr[i];
}
for (let i = 1; i < n + 1; i++) {
XOR ^= i;
}
return XOR;
}
// Driver code
const arr = [1, 2, 4, 5];
const n = 5;
console.log(findMissingNumbers(arr, n));
Output
3
Time Complexity : O(N)
Auxillary space: O(1)
Most Efficient Way to Find a Missing Number in an array ( in constant space and constant time)
In this approach we will create Function to find the missing number using the sum of natural numbers formula. First we will Calculate the total sum of the first N natural numbers using formula n * (n + 1) / 2. Now we calculate sum of all elements in given array. Subtract the total sum with sum of all elements in given array and return the missing number.
Below is the implementation of above approach:
#include <iostream>
#include <vector>
using namespace std;
int findMissingNumber(const vector<int>& nums)
{
// Calculate the total sum
int n = nums.size() + 1;
int totalSum = n * (n + 1) / 2;
// Calculate sum of all elements in the given array
int arraySum = 0;
for (int num : nums) {
arraySum += num;
}
// Subtract and return the total sum with the sum of
// all elements in the array
int missingNumber = totalSum - arraySum;
return missingNumber;
}
int main()
{
vector<int> numbers = { 1, 2, 3, 4, 5, 6, 7, 9 };
int missing = findMissingNumber(numbers);
cout << "The only missing number is: " << missing
<< endl;
return 0;
}
import java.util.Arrays;
public class Main {
// Function to find the missing number
public static int findMissingNumber(int[] nums)
{
// Calculate the total number of elements including
// the missing one
int n = nums.length + 1;
// Calculate the total sum using the formula for the
// sum of the first n natural numbers
int totalSum = n * (n + 1) / 2;
// Calculate the sum of all elements in the given
// array
int arraySum = Arrays.stream(nums).sum();
// Subtract the array sum from the total sum to find
// the missing number
int missingNumber = totalSum - arraySum;
// Return the missing number
return missingNumber;
}
// Main method
public static void main(String[] args)
{
int[] numbers = { 1, 2, 3, 4, 5, 6, 7, 9 };
int missing = findMissingNumber(numbers);
// Print the missing number
System.out.println("The only missing number is: "
+ missing);
}
}
def find_missing_number(nums):
# Calculate the total sum
n = len(nums) + 1
total_sum = n * (n + 1) // 2
# Calculate sum of all elements in the given array
array_sum = sum(nums)
# Subtract and return the total sum with the sum of
# all elements in the array
missing_number = total_sum - array_sum
return missing_number
if __name__ == "__main__":
numbers = [1, 2, 3, 4, 5, 6, 7, 9]
missing = find_missing_number(numbers)
print(f"The only missing number is: {missing}")
# This code is contributed by Ayush Mishra
// Function to find the missing number
function findMissingNumber(nums) {
// Calculate the total number of elements including the missing one
let n = nums.length + 1;
// Calculate the total sum using the formula for the sum of the first n natural numbers
let totalSum = n * (n + 1) / 2;
// Calculate the sum of all elements in the given array
let arraySum = nums.reduce((a, b) => a + b, 0);
// Subtract the array sum from the total sum to find the missing number
let missingNumber = totalSum - arraySum;
// Return the missing number
return missingNumber;
}
// Main execution starts here
let numbers = [1, 2, 3, 4, 5, 6, 7, 9];
let missing = findMissingNumber(numbers);
// Print the missing number
console.log(`The only missing number is: ${missing}`);
// This code is contributed by Ayush Mishra
Output
The only missing number is: 8
Time Complexity:O(1)
Auxiliary Space: O(1)
Contact Us