Find cells with odd values in a matrix

0 / 250
Matrix cells

Problem Statement:-

 

Given n and m which are the dimensions of a matrix initialized by zeros and given an array indices where indices[i] = [ri, ci]. For each pair of [ri, ci] you have to increment all cells in row ri and column ci by 1.

Return the number of cells with odd values in the matrix after applying the increment to all indices.

 

Example 1:

Matrix example 1

 

Input: n = 2, m = 3, indices = [[0,1],[1,1]]

Output: 6

Explanation: Initial matrix = [[0,0,0],[0,0,0]].

After applying first increment it becomes [[1,2,1],[0,1,0]].

The final matrix will be [[1,3,1],[1,3,1]] which contains 6 odd numbers.

 

Example 2:

Example 2

Matrix example 2

 

Input: n = 2, m = 2, indices = [[1,1],[0,0]]

Output: 0

Explanation: Final matrix = [[2,2],[2,2]]. There is no odd number in the final matrix.

 

Constraints:

  • 1 <= n <= 50
  • 1 <= m <= 50
  • 1 <= indices.length <= 100
  • 0 <= indices[i][0] < n
  • 0 <= indices[i][1] < m

 

 

Below is an algorithm in Javascript:

 

  • Initialize the output matrix

 

  • Loop through and extract the ith row and columns

 

  • Increment the cells in the ith row and ith columns obtained from previous step by 1

 

  • Check the matrix cells by looping through the entries, increment the counter if the entry is odd and return the count

 

/**
 * @param {number} n
 * @param {number} m
 * @param {number[][]} indices
 * @return {number}
 */
var oddCells = function(n, m, indices) {
    var matrix = zeros([n,m]);
    
    var count = 0;
    
    for (var i = 0; i < indices.length; i++) {
        var row = indices[i][0];
        var col = indices[i][1];
        
        matrix = incrementCells(n, m, row, col, matrix);
    }
    for (var i = 0; i < n; i++) {
        for (var j = 0; j < m; j++) {
            if (matrix[i][j] % 2 !== 0)
                count++;
        }
    }
    return count;
};

var incrementCells = function(n, m, row, col, matrix) {
    for (var i = 0; i < m; i++) {
        matrix[row][i]++;
    }
        
    for (var j = 0; j < n; j++) {
        matrix[j][col]++;
    }
   
    return matrix;
}

var zeros = function(dimensions) {
    var array = [];

    for (var i = 0; i < dimensions[0]; ++i) {
        array.push(dimensions.length == 1 ? 0 : zeros(dimensions.slice(1)));
    }

    return array;
}

 

Like us on:- Golibrary(fb) and follow on Linkedin to receive regular updates.

 

 

Comments

comments


An avid reader, responsible for generating creative content ideas for golibrary.co. His interests include algorithms and programming languages. Blogging is a hobby and passion.

Related Posts