Given a Zero matrix of N x N size, the task is to find the numbers of cells containing even numbers after performing Q queries. Each query will be in the form of (X, Y) such that for a given cell (X, Y), an increment operation has to be performed on all cells in the X’th row and Y’th column.
Note: The initial 0’s are also to be taken as even numbers in the count.
Examples:
Input: N = 2, Q = { {1, 1}, {1, 2}, {2, 1} }
Output: 2
Explanation:
In the first query, we add 1
to all elements of row 1 and column 1.
Our matrix become
2 1
1 0
In the second query, we add 1
to all elements of row 1 and column 2.
Our matrix become
3 3
1 1
In the last query, we add 1
to all elements of row 2 and column 1.
Our matrix finally become
4 3
3 2
In the final updated matrix, there
are 2 even numbers 4 and 3
respectively, hence ans is 2
Input: N = 2, Q = { {1, 1} }
Output: 1
Naive Approach: The Naive approach would be to update each and every cell in the matrix as per the query. Then traverse the matrix to find out the even cells.
Time Complexity: O(N2)
Efficient Approach:
- Maintain two arrays, one for rows operation and one for column operation.
- The row[i] will store the number of operations on i+1th row and col[i] will store the number of operations on i+1th column.
- If 1 is to be added to ith row, we will do row[i-1]++, assuming 0 based indexing.
- Same for columns.
- Now, we need to observe that odd + odd = even and even + even = even.
- Hence if row[i] and col[j] are both odd or even, then that cell will have even value.
- So we need to just count odd and even values in both arrays and multiply them.
Below is the implementation of above approach:
C++
// C++ program find Number of Even cells// in a Zero Matrix after Q queries#include <bits/stdc++.h>using namespace std;// Function to find the number of// even cell in a 2D matrixint findNumberOfEvenCells(int n, int q[][2], int size){ // Maintain two arrays, one for rows operation // and one for column operation int row[n] = { 0 }; int col[n] = { 0 }; for (int i = 0; i < size; i++) { int x = q[i][0]; int y = q[i][1]; // Increment operation on row[i] row[x - 1]++; // Increment operation on col[i] col[y - 1]++; } int r1 = 0, r2 = 0; int c1 = 0, c2 = 0; // Count odd and even values in // both arrays and multiply them for (int i = 0; i < n; i++) { // Count of rows having even numbers if (row[i] % 2 == 0) { r1++; } // Count of rows having odd numbers if (row[i] % 2 == 1) { r2++; } // Count of columns having even numbers if (col[i] % 2 == 0) { c1++; } // Count of columns having odd numbers if (col[i] % 2 == 1) { c2++; } } int count = r1 * c1 + r2 * c2; return count;}// Driver codeint main(){ int n = 2; int q[][2] = { { 1, 1 }, { 1, 2 }, { 2, 1 } }; int size = sizeof(q) / sizeof(q[0]); cout << findNumberOfEvenCells(n, q, size); return 0;} |
Java
// Java program find Number of Even cells // in a Zero Matrix after Q queries class GFG { // Function to find the number of // even cell in a 2D matrix static int findNumberOfEvenCells(int n, int q[][], int size) { // Maintain two arrays, one for rows operation // and one for column operation int row[] = new int[n] ; int col[] = new int[n] ; for (int i = 0; i < size; i++) { int x = q[i][0]; int y = q[i][1]; // Increment operation on row[i] row[x - 1]++; // Increment operation on col[i] col[y - 1]++; } int r1 = 0, r2 = 0; int c1 = 0, c2 = 0; // Count odd and even values in // both arrays and multiply them for (int i = 0; i < n; i++) { // Count of rows having even numbers if (row[i] % 2 == 0) { r1++; } // Count of rows having odd numbers if (row[i] % 2 == 1) { r2++; } // Count of columns having even numbers if (col[i] % 2 == 0) { c1++; } // Count of columns having odd numbers if (col[i] % 2 == 1) { c2++; } } int count = r1 * c1 + r2 * c2; return count; } // Driver code public static void main (String[] args) { int n = 2; int q[][] = { { 1, 1 }, { 1, 2 }, { 2, 1 } }; int size = q.length; System.out.println(findNumberOfEvenCells(n, q, size)); } }// This code is contributed by AnkitRai01 |
Python3
# Python3 program find Number of Even cells # in a Zero Matrix after Q queries # Function to find the number of # even cell in a 2D matrix def findNumberOfEvenCells(n, q, size) : # Maintain two arrays, one for rows operation # and one for column operation row = [0]*n ; col = [0]*n for i in range(size) : x = q[i][0]; y = q[i][1]; # Increment operation on row[i] row[x - 1] += 1; # Increment operation on col[i] col[y - 1] += 1; r1 = 0; r2 = 0; c1 = 0; c2 = 0; # Count odd and even values in # both arrays and multiply them for i in range(n) : # Count of rows having even numbers if (row[i] % 2 == 0) : r1 += 1; # Count of rows having odd numbers if (row[i] % 2 == 1) : r2 += 1; # Count of columns having even numbers if (col[i] % 2 == 0) : c1 +=1; # Count of columns having odd numbers if (col[i] % 2 == 1) : c2 += 1; count = r1 * c1 + r2 * c2; return count; # Driver code if __name__ == "__main__" : n = 2; q = [ [ 1, 1 ], [ 1, 2 ], [ 2, 1 ] ]; size = len(q); print(findNumberOfEvenCells(n, q, size)); # This code is contributed by AnkitRai01 |
C#
// C# program find Number of Even cells // in a Zero Matrix after Q queriesusing System;class GFG { // Function to find the number of // even cell in a 2D matrix static int findNumberOfEvenCells(int n, int [,]q, int size) { // Maintain two arrays, one for rows operation // and one for column operation int []row = new int[n] ; int []col = new int[n] ; for (int i = 0; i < size; i++) { int x = q[i, 0]; int y = q[i, 1]; // Increment operation on row[i] row[x - 1]++; // Increment operation on col[i] col[y - 1]++; } int r1 = 0, r2 = 0; int c1 = 0, c2 = 0; // Count odd and even values in // both arrays and multiply them for (int i = 0; i < n; i++) { // Count of rows having even numbers if (row[i] % 2 == 0) { r1++; } // Count of rows having odd numbers if (row[i] % 2 == 1) { r2++; } // Count of columns having even numbers if (col[i] % 2 == 0) { c1++; } // Count of columns having odd numbers if (col[i] % 2 == 1) { c2++; } } int count = r1 * c1 + r2 * c2; return count; } // Driver code public static void Main () { int n = 2; int [,]q = { { 1, 1 }, { 1, 2 }, { 2, 1 } }; int size = q.GetLength(0); Console.WriteLine(findNumberOfEvenCells(n, q, size)); } } // This code is contributed by AnkitRai01 |
Javascript
<script> // JavaScript program find Number of Even cells // in a Zero Matrix after Q queries // Function to find the number of // even cell in a 2D matrix function findNumberOfEvenCells(n, q, size) { // Maintain two arrays, one for rows operation // and one for column operation let row = new Array(n); row.fill(0); let col = new Array(n); col.fill(0); for (let i = 0; i < size; i++) { let x = q[i][0]; let y = q[i][1]; // Increment operation on row[i] row[x - 1]++; // Increment operation on col[i] col[y - 1]++; } let r1 = 0, r2 = 0; let c1 = 0, c2 = 0; // Count odd and even values in // both arrays and multiply them for (let i = 0; i < n; i++) { // Count of rows having even numbers if (row[i] % 2 == 0) { r1++; } // Count of rows having odd numbers if (row[i] % 2 == 1) { r2++; } // Count of columns having even numbers if (col[i] % 2 == 0) { c1++; } // Count of columns having odd numbers if (col[i] % 2 == 1) { c2++; } } let count = r1 * c1 + r2 * c2; return count; } let n = 2; let q = [ [ 1, 1 ], [ 1, 2 ], [ 2, 1 ] ]; let size = q.length; document.write(findNumberOfEvenCells(n, q, size)); </script> |
Output:
2
Time Complexity: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
