JavaScript Program to Find Missing Number in Matrix

JavaScript Program to Find the Missing Number

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.

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 &lt; n - 1; i++) {
    sumOfArray += flattenedArray[i];
}

const missingNumber = sumOfFirstN - sumOfArray;

console.log(&quot;Missing Number: &quot;, 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 size n + 1, where n is the length of the flattened array. Initialize all elements of temp 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.

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 &lt; n; i++) {
    temp[flattenedArray[i] - 1] = 1;
}

let missingNumber = 0;
for (let i = 0; i &lt;= n; i++) {
    if (temp[i] === 0) {
        missingNumber = i + 1;
        break;
         // Exit loop once missing number is found
    }
}

console.log(&quot;Missing Number:&quot;, 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.

JavaScript

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

Tags:

#JavaScript-DSA #JavaScript-Program #Geeks Premier League #JavaScript #Web Technologies

JavaScript Program to Find the Missing Number

JavaScript Program to Find Missing Number in Matrix

Approach 1: Using Summation of First N Natural Numbers

Approach 2: Using Hashing

Approach 3: XOR Method

Contact Us