Odd in Matrix
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
Resources
- Learning Python: From Zero to Hero
- Algorithms Problem Solving Series
- Stack Data Structure
- Queue Data Structure
- Linked List
- Tree Data Structure
Have fun, keep learning, and always keep coding!