Cells with Odd Values in a Matrix

🏠 ⬅️ ➡️

There is an m x n matrix that is initialized to all 0's. There is also a 2D array indices where each indices[i] = [ri, ci] represents a 0-indexed location to perform some increment operations on the matrix.

For each location indices[i], do both of the following:

  1. Increment all the cells on row ri.
  2. Increment all the cells on column ci.

Given m, n, and indices, return the number of odd-valued cells in the matrix after applying the increment to all locations in indices.

Example 1:

Input: m = 2, n = 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 is [[1,3,1],[1,3,1]], which contains 6 odd numbers.

Example 2:

Input: m = 2, n = 2, indices = [[1,1],[0,0]] Output: 0 Explanation: Final matrix = [[2,2],[2,2]]. There are no odd numbers in the final matrix.

Constraints:

  • 1 <= m, n <= 50
  • 1 <= indices.length <= 100
  • 0 <= ri < m
  • 0 <= ci < n

Follow up: Could you solve this in O(n + m + indices.length) time with only O(n + m) extra space?

Note: This problem is from LeetCode.
✅ Compiled
❌ Executed
❌ Correct 
program main
    ! Solves the problem described in the comment block
    implicit none

    integer :: m, n, i, j, ri, ci, num_odd
    integer, dimension(:, :), allocatable :: matrix
    integer, dimension(:, :), allocatable :: indices

    ! Read input
    read *, m, n
    allocate(matrix(m, n))
    allocate(indices(size(matrix, 1), size(matrix, 2)))
    do i = 1, size(matrix, 1)
        do j = 1, size(matrix, 2)
            read *, matrix(i, j)
        end do
    end do
    do i = 1, size(indices, 1)
        read *, indices(i, :)
    end do

    ! Apply increments
    do i = 1, size(indices, 1)
        ri = indices(i, 1)
        ci = indices(i, 2)
        matrix(ri, :) = matrix(ri, :) + 1
        matrix(:, ci) = matrix(:, ci) + 1
    end do

    ! Count number of odd values
    num_odd = 0
    do i = 1, size(matrix, 1)
        do j = 1, size(matrix, 2)
            if (mod(matrix(i, j), 2) /= 0) then
                num_odd = num_odd + 1
            end if
        end do
    end do

    ! Output result
    write (*, '(I0)') num_odd

end program main
✅ Compiled
❌ Executed
❌ Correct 
!DEC$ IF DEFINED (WINDOWS)
!DEC$ ATTRIBUTES STDCALL ::
!DEC$ ENDIF

PROGRAM OddCells

  IMPLICIT NONE

  INTEGER, PARAMETER :: INTEGER_SIZE = SELECTED_INT_KIND(9)
  INTEGER(KIND=INTEGER_SIZE) :: m, n, indices_size
  INTEGER(KIND=INTEGER_SIZE), DIMENSION(:,:), ALLOCATABLE :: matrix
  INTEGER(KIND=INTEGER_SIZE), DIMENSION(:,:), ALLOCATABLE :: indices
  INTEGER(KIND=INTEGER_SIZE) :: i, j, ri, ci, odd_count

  ! Read input
  READ(*,*) m, n, indices_size
  ALLOCATE(matrix(m,n))
  ALLOCATE(indices(indices_size,2))
  DO i = 1, m
    READ(*,*) matrix(i,:)
  END DO
  DO i = 1, indices_size
    READ(*,*) indices(i,:)
  END DO

  ! Apply increment operations
  DO i = 1, indices_size
    ri = indices(i,1)
    ci = indices(i,2)
    matrix(ri,:) = matrix(ri,:) + 1
    matrix(:,ci) = matrix(:,ci) + 1
  END DO

  ! Count odd numbers
  odd_count = 0
  DO i = 1, m
    DO j = 1, n
      IF (MOD(matrix(i,j),2) /= 0) odd_count = odd_count + 1
    END DO
  END DO

  ! Print output
  WRITE(*,*) odd_count

  ! Deallocate memory
  DEALLOCATE(matrix)
  DEALLOCATE(indices)

END PROGRAM OddCells
🌐 Data from online sources 
def break_palindrome(palindrome: str) -> str:
    n = len(palindrome)
    if n < 2:
        return ""

    palindrome = list(palindrome)
    for i in range(n // 2):
        if palindrome[i] != 'a':
            palindrome[i] = 'a'
            return "".join(palindrome)

    palindrome[-1] = 'b'
    return "".join(palindrome)

The algorithm starts by checking if the length of the input string is less than 2, in which case it returns an empty string, as there is no way to make it non-palindrome with a single character replacement.

Then, it iterates over the characters of the string up to the middle position (length / 2). If it finds a character different from 'a', it replaces the character with 'a' to ensure lexicographically smallest result, and returns the modified string.

If the loop ends and all characters up to the middle are 'a's, then it replaces the last character of the string with 'b' and returns the modified string. This ensures that the string is no longer a palindrome, and retains the lexicographically smallest property.

🌐 Data from online sources 
#include <string>

std::string breakPalindrome(std::string palindrome) {
    int n = palindrome.size();
    if (n < 2) return "";

    for (int i = 0; i < n / 2; i++) {
        if (palindrome[i] != 'a') {
            palindrome[i] = 'a';
            return palindrome;
        }
    }

    palindrome[n - 1] = 'b';
    return palindrome;
}

The algorithm starts by checking if the length of the input string is less than 2, in which case it returns an empty string, as there is no way to make it non-palindrome with a single character replacement.

Then, it iterates over the characters of the string up to the middle position (length / 2). If it finds a character different from 'a', it replaces the character with 'a' to ensure lexicographically smallest result, and returns the modified string.

If the loop ends and all characters up to the middle are 'a's, then it replaces the last character of the string with 'b' and returns the modified string. This ensures that the string is no longer a palindrome, and retains the lexicographically smallest property.