Dada una array arr[][] de tamaño NxM y un número entero K , la tarea es encontrar el recuento de subarrays cuadradas en la array dada con el promedio de elementos mayor o igual que K .
Ejemplos:
Entrada: K = 4, arr[][] = {{2, 2, 3}, {3, 4, 5}, {4, 5, 5}}
Salida: 7
Explicación:
Las siguientes subarrays cuadradas tienen un promedio mayor que o igual a K:
- Subarrays cuadradas de dimensión (1×1), formadas tomando los elementos en las posiciones {(2, 2)}. El promedio de la subarray es igual a 4.
- Subarrays cuadradas de dimensión (1×1), formadas tomando los elementos en las posiciones {(2, 3)}. El promedio de la subarray es igual a 5.
- Subarrays cuadradas de dimensión (1×1), formadas tomando los elementos en las posiciones {(3, 1)}. El promedio de la subarray es igual a 4.
- Subarrays cuadradas de dimensión (1×1), formadas tomando los elementos en las posiciones {(3, 2)}. El promedio de la subarray es igual a 5.
- Subarrays cuadradas de dimensión (1×1), formadas tomando los elementos en las posiciones {(3, 3)}. El promedio de la subarray es igual a 5.
- Subarrays cuadradas de dimensión (2×2), formadas tomando los elementos en las posiciones {(2, 1), (2, 2), (3, 1), (3, 2)}. El promedio de la subarray es igual a (3+4+4+5 = 16)/4 = 4.
- Subarrays cuadradas de dimensión (2×2), formadas tomando los elementos en las posiciones {(2, 2), (2, 3), (3, 2), (3, 3)}. El promedio de la subarray es igual a (4+5+5+5 = 19)/4 = 4,75.
Por lo tanto, hay totales de 7 subarrays cuadradas con un promedio mayor o igual a K.
Entrada: K = 3, arr[][] = {{1, 1, 1}, {1, 1, 1}}
Salida: 0
Enfoque ingenuo: el enfoque más simple es generar todas las subarrays cuadradas posibles y verificar que la suma de todos los elementos del subcuadrado sea mayor o igual a K multiplicado por el tamaño de la subarray.
Complejidad de Tiempo: O(N 3 * M 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando la array de suma de prefijos que da como resultado un cálculo de tiempo constante de la suma de una subarray. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos contar como 0 para almacenar el recuento de subarrays con un promedio mayor o igual a K .
- Calcule la suma del prefijo de la array arr[][] y guárdela en un vector de vectores , digamos pre[][] .
- Recorra cada elemento de la array usando las variables i y j y realice los siguientes pasos:
- Inicialice dos variables, digamos l como i y r como j .
- Iterar hasta que l y r sean mayores que 0 y en cada iteración realizar los siguientes pasos:
- Calcule la suma de la subarray cuadrada con el vértice inferior derecho como (i, j) y el vértice superior izquierdo como (l, r) y guárdelo en una variable, digamos sum , es decir sum = pre[i][j] – pre[l-1][r] – pre[l][r-1] + pre[l-1][r-1] .
- Ahora, si el valor de K*(i-l+1)*(j-r+1) es igual a la suma , entonces incremente el conteo en 1 .
- Disminuya l y r en 1 .
- Calcule la suma de la subarray cuadrada con el vértice inferior derecho como (i, j) y el vértice superior izquierdo como (l, r) y guárdelo en una variable, digamos sum , es decir sum = pre[i][j] – pre[l-1][r] – pre[l][r-1] + pre[l-1][r-1] .
- Finalmente, después de completar los pasos anteriores, imprima el valor de la cuenta como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; #define MAX 1000 // Function to count submatrixes with // average greater than or equals to K int cntMatrices(vector<vector<int> > arr, int N, int M, int K) { // Stores count of submatrices int cnt = 0; // Stores the prefix sum of matrix vector<vector<int> > pre(N + 1, vector<int>(M + 1, 0)); // Iterate over the range [1, N] for (int i = 1; i <= N; i++) { // Iterate over the range // [1, M] for (int j = 1; j <= M; j++) { // Update the prefix sum pre[i][j] = arr[i - 1][j - 1] + pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1]; } } // Iterate over the range [1, N] for (int i = 1; i <= N; i++) { // Iterate over the range // [1, M] for (int j = 1; j <= M; j++) { // Iterate until l and r // are greater than 0 for (int l = i, r = j; l > 0 && r > 0; l--, r--) { // Update count int sum1 = (K * (i - l + 1) * (i - r + 1)); // Stores sum of submatrix // with bottom right corner // as (i, j) and top left // corner as (l, r) int sum2 = pre[i][j] - pre[l - 1][r] - pre[l][r - 1] + pre[l - 1][r - 1]; // If sum1 is less than or // equal to sum2 if (sum1 <= sum2) // Increment cnt by 1 cnt++; } } } // Return cnt as the answer return cnt; } // Driver Code int main() { // Given Input vector<vector<int> > arr = { { 2, 2, 3 }, { 3, 4, 5 }, { 4, 5, 5 } }; int K = 4; int N = arr.size(); int M = arr[0].size(); // Function Call cout << cntMatrices(arr, N, M, K); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ static int MAX = 1000; // Function to count submatrixes with // average greater than or equals to K static int cntMatrices(int[][] arr, int N, int M, int K) { // Stores count of submatrices int cnt = 0; // Stores the prefix sum of matrix int[][] pre = new int[N + 1][M + 1]; // Iterate over the range [1, N] for(int i = 1; i <= N; i++) { // Iterate over the range // [1, M] for(int j = 1; j <= M; j++) { // Update the prefix sum pre[i][j] = arr[i - 1][j - 1] + pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1]; } } // Iterate over the range [1, N] for(int i = 1; i <= N; i++) { // Iterate over the range // [1, M] for(int j = 1; j <= M; j++) { // Iterate until l and r // are greater than 0 for(int l = i, r = j; l > 0 && r > 0; l--, r--) { // Update count int sum1 = (K * (i - l + 1) * (i - r + 1)); // Stores sum of submatrix // with bottom right corner // as (i, j) and top left // corner as (l, r) int sum2 = pre[i][j] - pre[l - 1][r] - pre[l][r - 1] + pre[l - 1][r - 1]; // If sum1 is less than or // equal to sum2 if (sum1 <= sum2) // Increment cnt by 1 cnt++; } } } // Return cnt as the answer return cnt; } // Driver Code public static void main(String args[]) { // Given Input int[][] arr = { { 2, 2, 3 }, { 3, 4, 5 }, { 4, 5, 5 } }; int K = 4; int N = arr.length; int M = arr[0].length; // Function Call System.out.println( cntMatrices(arr, N, M, K)); } } // This code is contributed by avijitmondal1998
Python3
# Python3 program for the above approach # define MAX 1000 # Function to count submatrixes with # average greater than or equals to K def cntMatrices(arr, N, M, K): # Stores count of submatrices cnt = 0 # Stores the prefix sum of matrix pre = [[0 for i in range(M + 1)] for i in range(N + 1)] # Iterate over the range [1, N] for i in range(1, N + 1): # Iterate over the range # [1, M] for j in range(1, M + 1): # Update the prefix sum pre[i][j] = (arr[i - 1][j - 1] + pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1]) # Iterate over the range [1, N] for i in range(1, N + 1): # Iterate over the range # [1, M] for j in range(1, M + 1): # Iterate until l and r # are greater than 0 l, r = i, j while l > 0 and r > 0: # Update count sum1 = (K * (i - l + 1) * (i - r + 1)) # Stores sum of submatrix # with bottom right corner # as (i, j) and top left # corner as (l, r) sum2 = (pre[i][j] - pre[l - 1][r] - pre[l][r - 1] + pre[l - 1][r - 1]) # If sum1 is less than or # equal to sum2 if (sum1 <= sum2): # Increment cnt by 1 cnt += 1 l -= 1 r -= 1 # Return cnt as the answer return cnt # Driver Code if __name__ == '__main__': # Given Input arr = [ [ 2, 2, 3 ], [ 3, 4, 5 ], [ 4, 5, 5 ] ] K = 4 N = len(arr) M = len(arr[0]) # Function Call print(cntMatrices(arr, N, M, K)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach using System; class GFG { static int MAX = 1000; // Function to count submatrixes with // average greater than or equals to K static int cntMatrices(int[,] arr, int N, int M, int K) { // Stores count of submatrices int cnt = 0; // Stores the prefix sum of matrix int[,] pre = new int[N + 1, M + 1]; // Iterate over the range [1, N] for(int i = 1; i <= N; i++) { // Iterate over the range // [1, M] for(int j = 1; j <= M; j++) { // Update the prefix sum pre[i, j] = arr[i - 1, j - 1] + pre[i - 1, j] + pre[i, j - 1] - pre[i - 1, j - 1]; } } // Iterate over the range [1, N] for(int i = 1; i <= N; i++) { // Iterate over the range // [1, M] for(int j = 1; j <= M; j++) { // Iterate until l and r // are greater than 0 for(int l = i, r = j; l > 0 && r > 0; l--, r--) { // Update count int sum1 = (K * (i - l + 1) * (i - r + 1)); // Stores sum of submatrix // with bottom right corner // as (i, j) and top left // corner as (l, r) int sum2 = pre[i, j] - pre[l - 1, r] - pre[l, r - 1] + pre[l - 1, r - 1]; // If sum1 is less than or // equal to sum2 if (sum1 <= sum2) // Increment cnt by 1 cnt++; } } } // Return cnt as the answer return cnt; } // Driver code public static void Main(string[] args) { // Given Input int[,] arr = { { 2, 2, 3 }, { 3, 4, 5 }, { 4, 5, 5 } }; int K = 4; int N = arr.GetLength(0); int M = arr.GetLength(0); // Function Call Console.WriteLine( cntMatrices(arr, N, M, K)); } } // This code is contributed by sanjoy_62.
Javascript
<script> // Javascript program for the above approach let MAX = 1000 // Function to count submatrixes with // average greater than or equals to K function cntMatrices(arr, N, M, K) { // Stores count of submatrices let cnt = 0; // Stores the prefix sum of matrix let pre = new Array(N + 1).fill(0).map(() => new Array(M + 1).fill(0)) // Iterate over the range [1, N] for (let i = 1; i <= N; i++) { // Iterate over the range // [1, M] for (let j = 1; j <= M; j++) { // Update the prefix sum pre[i][j] = arr[i - 1][j - 1] + pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1]; } } // Iterate over the range [1, N] for (let i = 1; i <= N; i++) { // Iterate over the range // [1, M] for (let j = 1; j <= M; j++) { // Iterate until l and r // are greater than 0 for (let l = i, r = j; l > 0 && r > 0; l--, r--) { // Update count let sum1 = (K * (i - l + 1) * (i - r + 1)); // Stores sum of submatrix // with bottom right corner // as (i, j) and top left // corner as (l, r) let sum2 = pre[i][j] - pre[l - 1][r] - pre[l][r - 1] + pre[l - 1][r - 1]; // If sum1 is less than or // equal to sum2 if (sum1 <= sum2) // Increment cnt by 1 cnt++; } } } // Return cnt as the answer return cnt; } // Driver Code // Given Input let arr = [[2, 2, 3], [3, 4, 5], [4, 5, 5]]; let K = 4; let N = arr.length; let M = arr[0].length; // Function Call document.write(cntMatrices(arr, N, M, K)); // This code is contributed by _saurabh_jaiswal. </script>
7
Complejidad de tiempo: O(M * N * (min(N, M))
Espacio auxiliar: O(M * N)
Publicación traducida automáticamente
Artículo escrito por dharanendralv23 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA