JavaScript Program to Find the Missing Number
Given an array of size N-1 with integers in the range of [1, N]. The task is to find the missing number from the first N integers. There are no duplicate elements allowed in the array.
Examples:
Input : arr = [1, 2, 3, 5]
Output : 4
Input : arr = [1, 4, 3, 2, 6, 5, 7, 10, 9]
Output : 8
Approach 1: Using the Mathematical Approach (Summation of first N natural Numbers)
The sum of the first N natural Numbers in a Range [1, N] is given by N * (N + 1) / 2.
To find the missing number, first find the sum of the first N natural number using the formula. And then use array traversal using a loop (for / while, …) and find the sum of array elements. At last, subtract the sum of array elements from the sum of natural numbers to find the missing element of an array.
Syntax:
missingElement = (N * (N + 1) / 1) - Sum of Array Elements
Example: The function findMissingNumber calculates the missing number in an array by finding the difference between the sum of the expected sequence and the sum of the array elements.
function findMissingNumber(arr) {
const n = arr.length + 1;
const sumOfFirstN = (n * (n + 1)) / 2;
let sumOfArray = 0;
for (let i = 0; i < n - 1; i++) {
sumOfArray = sumOfArray + arr[i];
}
let missingNumber = sumOfFirstN - sumOfArray;
return missingNumber;
}
const arr = [1, 2, 5, 4, 6, 8, 7];
const missingNumber = findMissingNumber(arr);
console.log("Missing Number: ", missingNumber);
Output
Missing Number: 3
Approach 2: Using Hashing
- Create an array temp[] of size N + 1 (where N is the length of array) with all initial values as 0.
- Traverse the input array arr[], and set the temp index frequency to 1, i.e. if(temp[arr[i]] == 0) temp[arr[i]] = 1
- Traverse temp[] and output the array element having value as 0 (This is the missing element).
Example:
// Function to find the missing number
function findMissing(arr, N) {
let i;
// Create an Array of size N
// and filled with 0
let temp = new Array(N).fill(0);
// If array element exist then
// set the frequency to 1
for (i = 0; i < N; i++) {
temp[arr[i] - 1] = 1;
}
let ans = 0;
for (i = 0; i <= N; i++) {
if (temp[i] === 0)
ans = i + 1;
}
console.log(ans);
}
// Driver code
let arr = [1, 3, 7, 5, 6, 2];
let n = arr.length;
// Function call
findMissing(arr, n);
Output
4
Approach 3: Using Sorting
- First we will sort the array in ascending order. Sorting will helps us identify the missing number because it allows us to easily find where the sequence breaks.
- Next we will iterate over the sorted array. For each element at index i, we compare it with i + 1. If they are not equal then i + 1 is the missing numbe.
function findMissingNumber(arr) {
arr.sort((a, b) => a - b);
for (let i = 0; i < arr.length; i++) {
if (arr[i] !== i + 1) {
return i + 1;
}
}
return arr.length + 1;
}
const numbers = [1, 2, 3, 4, 5, 6, 8, 9, 10];
const missingNumber = findMissingNumber(numbers);
console.log("The missing number is:", missingNumber);
Output
The missing number is: 7
Approach 4: Using XOR
Another efficient way to find the missing number is by using the XOR bitwise operation. This method takes advantage of the properties of XOR, which is both associative and commutative. XORing two identical numbers results in 0, and XORing a number with 0 results in the number itself.
Example:
function findMissingNumber(arr) {
const n = arr.length + 1;
// Step 1: Calculate XOR of all numbers from 1 to N
let xor_all = 0;
for (let i = 1; i <= n; i++) {
xor_all ^= i;
}
// Step 2: Calculate XOR of all elements in the array
let xor_arr = 0;
for (let i = 0; i < arr.length; i++) {
xor_arr ^= arr[i];
}
// Step 3: XOR of xor_all and xor_arr gives the missing number
const missingNumber = xor_all ^ xor_arr;
return missingNumber;
}
// Test case
const arr = [1, 2, 3, 5];
const missingNumber = findMissingNumber(arr);
console.log("Missing Number: ", missingNumber);
const arr2 = [1, 4, 3, 2, 6, 5, 7, 10, 9];
const missingNumber2 = findMissingNumber(arr2);
console.log("Missing Number: ", missingNumber2);
Output
Missing Number: 4 Missing Number: 8