## DEV Community is a community of 699,738 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Algorithms Problem Solving: Odd in Matrix

TK
Sharing knowledge https://leandrotk.github.io
Originally published at leandrotk.github.io ・2 min read

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

• Initialize the matrix with all elements as zero
• For each pair of indices, increment for the row, and increment for the column
• Traverse the matrix counting all the odd numbers
• Return the counter
``````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
``````

## Discussion (3)

d33w

Don't you think there can be a better approach to this problem?

Elcio Ferreira

"Better" is a subjective concept. Some could call better this approach:

``````def odd_cells(n, m, indices):
matrix = [[0] * m for _ in range(n)]

for (ri, ci) in indices:
for col in range(len(matrix[ri])):
matrix[ri][col] ^= 1

for row in matrix:
row[ci] ^= 1

return sum([sum(line) for line in matrix])
``````

You can say it's better because it's shorter and faster. But it's much harder to read. If I am asked to maintain it, I would prefer much more TK's approach.

Or something like this:

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

for (ri, ci) in indices:
increment_matrix(matrix, ri, ci)

return sum_odds(matrix)

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

def increment_matrix(matrix, ri, ci):
for col in range(len(matrix[ri])):
matrix[ri][col] += 1

for row in matrix:
row[ci] += 1

def sum_odds(matrix):
odds = 0

for line in matrix:
odds += sum([(cell % 2) for cell in line])

return odds
``````

A lot more code, but way easier to read and understand, in my opinion.

Therefore, I ask you the same: don't you think there can be a better approach to this problem? How would you solve it?

Nam H. Le

I believe that there is a solution use only 4 numbers: number of columns (rows) which have even (odd) cells on each. Need time to test it...