Home

Odd in Matrix

Matrix Photo by Markus Spiske

This post is part of the Algorithms Problem Solving series.

Problem description

This is the Odd in Matrix problem. The description looks like this:

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.

Examples

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

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

Solution

def init_matrix(rows, columns):
    return [[0 for _ in range(columns)] for _ in range(rows)]

def odd_cells(n, m, indices):
    matrix = init_matrix(n, m)

    for [ri, ci] in indices:
        for column in range(m):
            matrix[ri][column] += 1

        for row in range(n):
            matrix[row][ci] += 1

    odds = 0

    for row in range(n):
        for column in range(m):
            if matrix[row][column] % 2 != 0:
                odds += 1

    return odds

Resources

Patreon Become a Patron Coffee icon Buy me a coffee