JavaScript Program to Find Missing Number in Matrix
You are presented with a two-dimensional matrix, matrix[][]
where each row contains an ordered sequence of positive integers. The task is to find the missing number in the matrix.
NOTE: Each row is a sequence of unique positive integers, arranged in ascending order.
Approach 1: Using Summation of First N Natural Numbers
- Flatten the Matrix: Convert the 2D matrix into a 1D array to work with the numbers more easily.
- Calculate Expected Total: Determine the total sum of the first N natural numbers (1 to N), where N is the length of the flattened array plus one.
- Calculate Actual Sum: Iterate through the flattened array and compute the sum of its elements.
- Find the Missing Number: Subtract the actual sum from the expected total to find the missing number.
- Display the Result: Print the missing number to the console.
We know,
Sum of first n natural numbers is (n * (n + 1)) / 2;
Example: In this example, the code efficiently calculates and finds the missing number in a 2D matrix by comparing the expected and actual sums of the numerical sequence using JavaScript.
const matrix = [
[1, 2],
[4, 5],
[6, 8],
[7, 9]
];
const flattenedArray = matrix.flat();
const n = flattenedArray.length + 1;
const sumOfFirstN = (n * (n + 1)) / 2;
let sumOfArray = 0;
for (let i = 0; i < n - 1; i++) {
sumOfArray += flattenedArray[i];
}
const missingNumber = sumOfFirstN - sumOfArray;
console.log("Missing Number: ", missingNumber);
Output
Missing Number: 3
Approach 2: Using Hashing
- Flatten the Matrix: Convert the 2D matrix into a 1D array to work with individual elements more easily.
- Create a Temporary Array: Create a temporary array
temp
of sizen + 1
, wheren
is the length of the flattened array. Initialize all elements oftemp
to 0. - Mark Existing Numbers: Iterate through the flattened array. For each element, set the corresponding index in the
temp
array to 1, indicating that the number exists in the sequence. - Find the Missing Number: Iterate through the
temp
array. The first index with a value of 0 corresponds to the missing number. Add 1 to the index to get the missing number itself. - Display the Result: Print the missing number to the console.
Example: In this example, the code efficiently finds the missing number in a 2D matrix by marking existing numbers and identifying the missing one using JavaScript.
const matrix = [
[1, 2],
[3, 4],
[6, 7]
];
const flattenedArray = matrix.flat();
let n = flattenedArray.length;
let temp = new Array(n + 1).fill(0);
// If array element exists then set the frequency to 1
for (let i = 0; i < n; i++) {
temp[flattenedArray[i] - 1] = 1;
}
let missingNumber = 0;
for (let i = 0; i <= n; i++) {
if (temp[i] === 0) {
missingNumber = i + 1;
break;
// Exit loop once missing number is found
}
}
console.log("Missing Number:", missingNumber);
Output
Missing Number: 5
Approach 3: XOR Method
- Flatten the Matrix: Convert the 2D matrix into a 1D array for easier processing.
- Initialize XOR Variables: Initialize two variables to store the XOR of all numbers in the flattened array and the XOR of the first N natural numbers.
- Compute XORs: XOR all elements of the flattened array. XOR all numbers from 1 to N (where N is the total number of expected elements).
- Find the Missing Number: XOR the two results. The final result will be the missing number because all paired numbers will cancel each other out, leaving only the missing number.
// Nikunj Sonigara
function findMissingNumber(matrix) {
// Flatten the matrix into a 1D array
const flattenedArray = matrix.flat();
const n = flattenedArray.length + 1; // Include the missing number
// Initialize XOR variables
let xorArray = 0;
let xorNatural = 0;
// Compute XOR of all elements in the flattened array
for (let i = 0; i < flattenedArray.length; i++) {
xorArray ^= flattenedArray[i];
}
// Compute XOR of all numbers from 1 to n
for (let i = 1; i <= n; i++) {
xorNatural ^= i;
}
// The missing number is the XOR of xorArray and xorNatural
const missingNumber = xorArray ^ xorNatural;
return missingNumber;
}
// Test matrices
const matrix1 = [
[1, 2],
[4, 5],
[6, 8],
[7, 9]
];
console.log("Missing Number in matrix1:", findMissingNumber(matrix1)); // Output: 3
const matrix2 = [
[1, 2],
[3, 4],
[6, 7]
];
console.log("Missing Number in matrix2:", findMissingNumber(matrix2)); // Output: 5
Output
Missing Number in matrix1: 3 Missing Number in matrix2: 5