Cuente el número de subarrays cuadradas de una array dada cuya suma de todas las celdas es igual a S | conjunto 2

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:
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:
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.
  • 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *