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
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.