DEV Community

Cover image for Algorithms Problem Solving: Odd in Matrix
TK
TK

Posted on • Originally published at leandrotk.github.io

Algorithms Problem Solving: Odd in Matrix

#algorithms #python #computerscience #interview

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Resources

Top comments (3)

Collapse
 
d33w profile image
d33w •

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

Collapse
 
elcio profile image
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?

Collapse
 
namhle profile image
Nam Hoang 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...

Read next

mrcaption49 profile image

CRUD FUNCTIONALITY in Django

Pranav Bakare -

dchaley profile image

Performance trap: general libraries & helper objects

David Haley -

grayhat profile image

LuxDevHQ (Lux Academy and Data Science East Africa) Training Program in AI, Data Science, Analytics, and Data Engineering

Mwenda Harun Mbaabu -

hakeem profile image

Concurrency and Parallelism in Python

Hakeem Abbas -