JavaScript Program to Find the Missing Number in a Given Integer Array of 1 to 100
In this article, we are going to find the missing number in a given integer array of 1 to 100 in JavaScript, Given an array [] of size 100 with integers in the range of [1, 100], There are no duplicate values in the array and no larger value than the size of the array. The task is to print that which is missing value in the array.
Let’s take an example:
Input: arr[] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, /* Missing number */,12, /* ... */, 100]; Size of an array is 100
Output: 11
Explanation: The missing number between 1 to 100 is 11
There are several methods that can be used to find the missing number in a given integer array of 1 to 100 in JavaScript, which are listed below:
Table of Content
- Approach 1: Using the Mathematical Formulae
- Approach 2: Using the array iteration
- Approach 3: Using Object
- Approach 4: Using Bit Manipulation (XOR)
We will explore all the above methods along with their basic implementation with the help of examples.
Approach 1: Using the Mathematical Formulae
Expected Sum = (n * (n + 1)) / 2
- n is the highest number in the range.
- Add 1 to n to include it in the summation.
- Multiply n by (n + 1).
- Divide the result by 2 to get the expected sum.
In this approach, we find the Sum of the Natural number of 1 to 100 using the sum of natural number formulae n(n+1)/2.After the sum of the natural number. Then calculate the sum of the given elements of the array. Now Subtract the sum of natural numbers – the sum of the given elements of the array. Then It will give the missing number.
Syntax:
const sumOfFirstN = (n * (n + 1)) / 2;
Example: In this example, we are using the above-explained approach.
function findMissingNumber(arr) {
const n = 100;
const sumOfFirstN = (n * (n + 1)) / 2;
const sumOfArray =
arr.reduce((acc, num) => acc + num, 0);
const missingNumber =
sumOfFirstN - sumOfArray;
return missingNumber;
}
const array =
Array.from({ length: 99 }, (_, index) => index + 1);
const missingNumber = findMissingNumber(array);
console.log("Missing number is:", missingNumber);
Output
Missing number is: 100
Approach 2: Using the array iteration
This approach involves iterating through the array and checking for the missing number. It is suitable when there are multiple missing numbers, but it is less efficient compared to the mathematical formula for finding a single missing number.
- Create a new Set which is containing numbers from 1 to 100.
- Iterate through the array and remove each element from the set
- After the iteration, you will get the missing number because that number is not found in the set. Then return the number.
Syntax:
function missingNumber(arr) {
for (let i = 1; i <= 100; i++) {
// code...
}
}
Example: In this example, we are using the above-explained approach.
function findMissingNumber(arr) {
const n = 100;
const allNumbers =
new Set(Array.from({ length: n }, (_, i) => i + 1));
for (const num of arr) {
allNumbers.delete(num);
}
// At this point, the 'allNumbers'
//set contains only the missing number(s).
const missingNumbers = Array.from(allNumbers);
return missingNumbers;
}
// Remove 66 value from this array
const array = [
1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
41, 42, 43, 44, 45, 46, 47, 48, 49, 50,
51, 52, 53, 54, 55, 56, 57, 58, 59, 60,
61, 62, 63, 64, 65, 67, 68, 69, 70,
71, 72, 73, 74, 75, 76, 77, 78, 79, 80,
81, 82, 83, 84, 85, 86, 87, 88, 89, 90,
91, 92, 93, 94, 95, 96, 97, 98, 99, 100
];
const missingNumber = findMissingNumber(array);
console.log("Missing number is:", missingNumber);
Output
Missing number is: [ 66 ]
Approach 3: Using Object
Using an Object to track number’s presence, iterate through 1 to 100, and return the first missing number from the given array.
Syntax:
function missingNumber(arr) {
const numberObj = {};
//code
}
Example: In this example, the missingNumber function finds the first missing number from 1 to 100 in the given array integer using an object for tracking.
function missingNumber(arr) {
const numberObj = {};
for (const num of arr) {
numberObj[num] = true;
}
for (let i = 1; i <= 100; i++) {
if (!numberObj[i]) {
return i;
}
}
}
const integer = [1, 2, 3, 4,/* ... */, 99, 100];
const result = missingNumber(integer);
console.log("Missing number:", result);
Output
Missing number: 5
Approach 4: Using Bit Manipulation (XOR)
This approach uses the XOR operation to find the missing number efficiently. The XOR operation has the property that it cancels out duplicate numbers, which we can leverage to find the missing number.
Steps:
- Initialize two variables, xorFull and xorArray.
- XOR all numbers from 1 to 100 and store the result in xorFull.
- XOR all the numbers in the given array and store the result in xorArray.
- XOR the results of xorFull and xorArray. The result will be the missing number.
Example: In this example, we will remove a random number from the array and use the bit manipulation approach to find the missing number.
function findMissingNumber(arr) {
const n = 100;
let xorFull = 0;
let xorArray = 0;
for (let i = 1; i <= n; i++) {
xorFull ^= i;
}
for (const num of arr) {
xorArray ^= num;
}
const missingNumber = xorFull ^ xorArray;
return missingNumber;
}
// Example array with 99 elements, removing the number 55
const array = Array.from({ length: 54 }, (_, index) => index + 1)
.concat(Array.from({ length: 45 }, (_, index) => index + 56));
const missingNumber = findMissingNumber(array);
console.log("Missing number is:", missingNumber);
Output
Missing number is: 55
Contact Us