Cells with Odd Values in a Matrix

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 a row ri and column ci by 1.
Find the number of cells with odd values in the matrix after applying the increment to all indices
Example 1:
Input: n = 2, m = 3, indices = [[0,1],[1,1]]
Output: 6

Approach

Java

public class CellsOddValuesInMatrix {
    public static void main(String[] args) {
        int n = 2, m = 3;
        int indices[][] = { { 01 }, { 11 } };
        System.out.println(oddCells(n, m, indices));
    }

    static int oddCells(int nint mint[][] indices) {
        int grid[][] = new int[n][m];
        for (int i = 0; i < indices.length; i++) {
            int x = indices[i][0];
            int y = indices[i][1];
            for (int k = 0; k < m; k++)
                grid[x][k]++;
            for (int k = 0; k < n; k++)
                grid[k][y]++;
        }
        int cnt = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                // odd value
                if (grid[i][j] % 2 != 0)
                    cnt++;
        return cnt;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;


int oddCells(int nint mvector<vector<int>>& indices
{
        int grid[n][m];
        memset(grid,0,sizeof(grid));
        for(int i=0;i<indices.size();i++)
         {
            int x=indices[i][0];
            int y=indices[i][1];
            for(int k=0;k<m;k++)
                   grid[x][k]++;
            for(int k=0;k<n;k++)
                   grid[k][y]++;
         }
        int cnt=0;
        for(int i=0;i<n;i++)
              for(int j=0;j<m;j++)
                     if(grid[i][j]&1)
                            cnt++;
        return cnt;
int main()
{
   int n = 2m = 3;
   vector<vector<int>> indices ={{0,1},{1,1}};
   cout<<oddCells(n,m,indices);
   return 0;
}


No comments:

Post a Comment