Dada una array , arr[][] de dimensiones M*N, y un entero S , la tarea es imprimir el conteo del número de subcuadrados de la array, cuya suma es igual a S .
Ejemplos:
Entrada: M = 4, N = 5, S = 10, array[][]={{2, 4, 3, 2, 10}, {3, 1, 1, 1, 5}, {1, 1, 2, 1, 4}, {2, 1, 1, 1, 3}}
Salida: 3
Explicación:
Subcuadrados {10}, {{2, 4}, {3, 1}} y {{1, 1 , 1}, {1, 2, 1}, {1, 1, 1}} tienen sumas iguales a 10.Entrada: M = 3, N = 4, S = 8, array[][]={{3, 1, 5, 3}, {2, 2, 2, 6}, {1, 2, 2, 4} }
Salida: 2
Explicación:
Los subcuadrados {{2, 2}, {2, 2}} y {{3, 1}, {2, 2}} tienen sumas iguales a 8.
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los subcuadrados posibles y verificar que la suma de todos los elementos del subcuadrado sea igual a S .
Complejidad de Tiempo: O(N 3 * M 3 )
Espacio Auxiliar: O(1)
Enfoque alternativo: el enfoque anterior se puede optimizar encontrando la suma del prefijo de una array que da como resultado el cálculo de tiempo constante de la suma de todos los elementos de la subarray. Siga los pasos a continuación para resolver el problema:
- Encuentre la suma del prefijo de la array arr[][] y guárdela en un vector 2D, por ejemplo, dp de dimensión (M + 1)*(N + 1).
- Inicialice una variable, digamos contar como 0 , para almacenar el recuento de subcuadrados con suma S.
- Iterar sobre el rango [1, min(N, M)] usando una variable x y realizar las siguientes operaciones:
- Itere sobre cada elemento de la array arr[][] usando las variables i y j y realice las siguientes operaciones:
- Si i y j son mayores o iguales que x , encuentre la suma de subcuadrados de dimensión x * x con (i, j) como el vértice inferior derecho en una variable, digamos Suma.
- Actualice la variable Sum como , Sum = dp[i][j] – dp[i – x][j] – dp[i][j – x] + dp[i – x][j – x].
- Si la Suma es igual a S, entonces incremente el conteo en 1.
- Itere sobre cada elemento de la array arr[][] usando las variables i y j y realice las siguientes operaciones:
- Finalmente, después de completar los pasos anteriores, imprima el valor en cuenta como la respuesta .
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;
// Function to compute prefix sum
void find_prefixsum(int M, int N, vector<vector<int> >& arr,
vector<vector<int> >& dp)
{
// Assign 0 to first column
for (int i = 0; i <= M; i++) {
dp[i][0] = 0;
}
// Assign 0 to first row
for (int j = 0; j <= N; j++) {
dp[0][j] = 0;
}
// Iterate over the range
//[1, M]
for (int i = 1; i <= M; i++) {
// Iterate over the range
//[1, N]
for (int j = 1; j <= N; j++) {
// Update
dp[i][j] = dp[i][j - 1] + arr[i - 1][j - 1];
}
}
// Iterate over the range
//[1, M]
for (int i = 1; i <= M; i++) {
// Iterate over the range
//[1, N]
for (int j = 1; j <= N; j++) {
// Update
dp[i][j] = dp[i][j] + dp[i - 1][j];
}
}
}
// Function to find sub-squares
// with given sum S
int findSubsquares(vector<vector<int> > arr, int M, int N,
int S)
{
// Stores the prefix sum of
// matrix
vector<vector<int> > dp(M + 1, vector<int>(N + 1));
// Function call to find
// prefix Sum of matrix
find_prefixsum(M, N, arr, dp);
// Stores the count of
// subsquares with sum S
int cnt = 0;
for (int x = 1; x <= min(N, M); x++) {
// Iterate over every
// element of the matrix
for (int i = x; i <= M; i++) {
for (int j = x; j <= N; j++) {
// Stores the sum of
// subsquare of dimension
// x*x formed with i, j as
// the bottom-right
// vertex
int sum = dp[i][j] - dp[i - x][j]
- dp[i][j - x] + dp[i - x][j - x];
// If sum is equal to S
if (sum == S) {
// Increment cnt by 1
cnt++;
}
}
}
}
// Return the result
return cnt;
}
// Driver Code
int main()
{
// Input
int M = 4, N = 5;
vector<vector<int> > arr = { { 2, 4, 3, 2, 10 },
{ 3, 1, 1, 1, 5 },
{ 1, 1, 2, 1, 4 },
{ 2, 1, 1, 1, 3 } };
int S = 10;
// Function call
cout << findSubsquares(arr, M, N, S);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG
{
// Function to compute prefix sum
static void find_prefixsum(int M, int N, int[][] arr,int[][] dp)
{
// Assign 0 to first column
for (int i = 0; i <= M; i++) {
dp[i][0] = 0;
}
// Assign 0 to first row
for (int j = 0; j <= N; j++) {
dp[0][j] = 0;
}
// Iterate over the range
//[1, M]
for (int i = 1; i <= M; i++) {
// Iterate over the range
//[1, N]
for (int j = 1; j <= N; j++) {
// Update
dp[i][j] = dp[i][j - 1] + arr[i - 1][j - 1];
}
}
// Iterate over the range
//[1, M]
for (int i = 1; i <= M; i++) {
// Iterate over the range
//[1, N]
for (int j = 1; j <= N; j++) {
// Update
dp[i][j] = dp[i][j] + dp[i - 1][j];
}
}
}
// Function to find sub-squares
// with given sum S
static int findSubsquares(int[][] arr, int M, int N,int S)
{
// Stores the prefix sum of
// matrix
int[][] dp = new int[M + 1][N + 1];
// Function call to find
// prefix Sum of matrix
find_prefixsum(M, N, arr, dp);
// Stores the count of
// subsquares with sum S
int cnt = 0;
for (int x = 1; x <= Math.min(N, M); x++) {
// Iterate over every
// element of the matrix
for (int i = x; i <= M; i++) {
for (int j = x; j <= N; j++) {
// Stores the sum of
// subsquare of dimension
// x*x formed with i, j as
// the bottom-right
// vertex
int sum = dp[i][j] - dp[i - x][j]
- dp[i][j - x] + dp[i - x][j - x];
// If sum is equal to S
if (sum == S) {
// Increment cnt by 1
cnt++;
}
}
}
}
// Return the result
return cnt;
}
// Driver Code
public static void main(String[] args) {
// Input
int M = 4, N = 5;
int[][] arr = { { 2, 4, 3, 2, 10 },
{ 3, 1, 1, 1, 5 },
{ 1, 1, 2, 1, 4 },
{ 2, 1, 1, 1, 3 } };
int S = 10;
// Function call
System.out.println(findSubsquares(arr, M, N, S));
}
}
// This code is contributed by shinjanpatra
Python3
# python program for the above approach # Function to compute prefix sum def find_prefixsum(M, N, arr, dp): # Assign 0 to first column for i in range(0, M+1): dp[i][0] = 0 # Assign 0 to first row for j in range(0, N+1): dp[0][j] = 0 # Iterate over the range # [1, M] for i in range(1, M+1): # Iterate over the range # [1, N] for j in range(1, N+1): dp[i][j] = dp[i][j - 1] + arr[i - 1][j - 1] # Iterate over the range # [1, M] for i in range(1, M+1): # Iterate over the range # [1, N] for j in range(1, N+1): # Update dp[i][j] = dp[i][j] + dp[i - 1][j] # Function to find sub-squares # with given sum S def findSubsquares(arr, M, N, S): # Stores the prefix sum of # matrix dp = [[0 for i in range(N + 1)] for col in range(M + 1)] # Function call to find # prefix Sum of matrix find_prefixsum(M, N, arr, dp) # Stores the count of # subsquares with sum S cnt = 0 for x in range(1, min(N, M)): # Iterate over every # element of the matrix for i in range(x, M + 1): for j in range(x, N + 1): # Stores the sum of # subsquare of dimension # x*x formed with i, j as # the bottom-right # vertex sum = dp[i][j] - dp[i - x][j] - dp[i][j - x] + dp[i - x][j - x] # If sum is equal to S if (sum == S): # Increment cnt by 1 cnt += 1 # Return the result return cnt # Driver Code # Input M = 4 N = 5 arr = [[2, 4, 3, 2, 10], [3, 1, 1, 1, 5], [1, 1, 2, 1, 4], [2, 1, 1, 1, 3]] S = 10 # Function call print(findSubsquares(arr, M, N, S)) # This code is contributed by amreshkumar3
C#
// C# program for the above approach
using System;
class GFG {
// Function to compute prefix sum
static void find_prefixsum(int M, int N, int[, ] arr,
int[, ] dp)
{
// Assign 0 to first column
for (int i = 0; i <= M; i++) {
dp[i, 0] = 0;
}
// Assign 0 to first row
for (int j = 0; j <= N; j++) {
dp[0, j] = 0;
}
// Iterate over the range
//[1, M]
for (int i = 1; i <= M; i++) {
// Iterate over the range
//[1, N]
for (int j = 1; j <= N; j++) {
// Update
dp[i, j] = dp[i, j - 1] + arr[i - 1, j - 1];
}
}
// Iterate over the range
//[1, M]
for (int i = 1; i <= M; i++) {
// Iterate over the range
//[1, N]
for (int j = 1; j <= N; j++) {
// Update
dp[i, j] = dp[i, j] + dp[i - 1, j];
}
}
}
// Function to find sub-squares
// with given sum S
static int findSubsquares(int[, ] arr, int M, int N,
int S)
{
// Stores the prefix sum of
// matrix
int[, ] dp = new int[M + 1, N + 1];
// Function call to find
// prefix Sum of matrix
find_prefixsum(M, N, arr, dp);
// Stores the count of
// subsquares with sum S
int cnt = 0;
for (int x = 1; x <= Math.Min(N, M); x++) {
// Iterate over every
// element of the matrix
for (int i = x; i <= M; i++) {
for (int j = x; j <= N; j++) {
// Stores the sum of
// subsquare of dimension
// x*x formed with i, j as
// the bottom-right
// vertex
int sum = dp[i, j] - dp[i - x, j]
- dp[i, j - x]
+ dp[i - x, j - x];
// If sum is equal to S
if (sum == S) {
// Increment cnt by 1
cnt++;
}
}
}
}
// Return the result
return cnt;
}
// Driver Code
public static void Main()
{
// Input
int M = 4, N = 5;
int[, ] arr = { { 2, 4, 3, 2, 10 },
{ 3, 1, 1, 1, 5 },
{ 1, 1, 2, 1, 4 },
{ 2, 1, 1, 1, 3 } };
int S = 10;
// Function call
Console.WriteLine(findSubsquares(arr, M, N, S));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Javascript program for the above approach
// Function to compute prefix sum
function find_prefixsum(M, N, arr, dp)
{
// Assign 0 to first column
for (var i = 0; i <= M; i++) {
dp[i][0] = 0;
}
// Assign 0 to first row
for (var j = 0; j <= N; j++) {
dp[0][j] = 0;
}
// Iterate over the range
//[1, M]
for (var i = 1; i <= M; i++) {
// Iterate over the range
//[1, N]
for (var j = 1; j <= N; j++) {
// Update
dp[i][j] = dp[i][j - 1] + arr[i - 1][j - 1];
}
}
// Iterate over the range
//[1, M]
for (var i = 1; i <= M; i++) {
// Iterate over the range
//[1, N]
for (var j = 1; j <= N; j++) {
// Update
dp[i][j] = dp[i][j] + dp[i - 1][j];
}
}
}
// Function to find sub-squares
// with given sum S
function findSubsquares(arr, M, N, S)
{
// Stores the prefix sum of
// matrix
var dp = Array.from(Array(M+1), ()=>Array(N+1));
// Function call to find
// prefix Sum of matrix
find_prefixsum(M, N, arr, dp);
// Stores the count of
// subsquares with sum S
var cnt = 0;
for (var x = 1; x <= Math.min(N, M); x++) {
// Iterate over every
// element of the matrix
for (var i = x; i <= M; i++) {
for (var j = x; j <= N; j++) {
// Stores the sum of
// subsquare of dimension
// x*x formed with i, j as
// the bottom-right
// vertex
var sum = dp[i][j] - dp[i - x][j]
- dp[i][j - x] + dp[i - x][j - x];
// If sum is equal to S
if (sum == S) {
// Increment cnt by 1
cnt++;
}
}
}
}
// Return the result
return cnt;
}
// Driver Code
// Input
var M = 4, N = 5;
var arr = [ [ 2, 4, 3, 2, 10 ],
[ 3, 1, 1, 1, 5 ],
[ 1, 1, 2, 1, 4 ],
[ 2, 1, 1, 1, 3 ] ];
var S = 10;
// Function call
document.write( findSubsquares(arr, M, N, S));
// This code is contributed by rrrtnx.
</script>
Producción
3
Complejidad de Tiempo: O(M * N * min(M, N))
Espacio Auxiliar: O(N * M)
Enfoque eficiente: el enfoque anterior se puede optimizar aún más utilizando un algoritmo de búsqueda binaria . Consulte el enlace para la solución eficiente [ Recuento de subarray con suma X en una array dada ].
Publicación traducida automáticamente
Artículo escrito por lokeshpotta20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA