Dada una array cero de tamaño N x N , la tarea es encontrar el número de celdas que contienen números pares después de realizar consultas Q. Cada consulta tendrá la forma de (X, Y), de modo que para una celda determinada (X, Y), se debe realizar una operación de incremento en todas las celdas de la fila X y la columna Y.
Nota: Los 0 iniciales también deben tomarse como números pares en el conteo.
Ejemplos:
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
Enfoque ingenuo: el enfoque ingenuo sería actualizar todas y cada una de las celdas de la array según la consulta. Luego atraviesa la array para encontrar las celdas pares.
Complejidad de tiempo: O(N 2 )
Enfoque eficiente:
- Mantenga dos arreglos, uno para operación de filas y otro para operación de columna.
- La fila [i] almacenará el número de operaciones en la fila i+1 y col[i] almacenará el número de operaciones en la columna i+ 1 .
- Si se va a agregar 1 a la i -ésima fila, haremos fila[i-1]++, asumiendo una indexación basada en 0.
- Lo mismo para las columnas.
- Ahora, necesitamos observar que impar + impar = par y par + par = par.
- Por lo tanto, si la fila [i] y la columna [j] son pares o impares, entonces esa celda tendrá un valor par.
- Entonces, solo necesitamos contar los valores pares e impares en ambas arrays y multiplicarlos.
A continuación se muestra la implementación del enfoque anterior:
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 matrix
int 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 code
int 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 queries
using 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>
Producción:
2
Complejidad de tiempo: O(N)
Publicación traducida automáticamente
Artículo escrito por SnehashishKalamkar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA