Dada una array de tamaño N x M y un número entero X , la tarea es encontrar el número de subcuadrados en la array con suma de elementos igual a X.
Ejemplos:
Entrada: N = 4, M = 5, X = 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:
{10}, {{2, 4}, {3, 1}} y {{1, 1, 1} , {1, 2, 1}, {1, 1, 1}} son subcuadrados con suma 10.
Entrada: N = 3, M = 4, X = 8, arr[][]={{3, 1, 5 , 3}, {2, 2, 2, 6}, {1, 2, 2, 4}}
Salida: 2
Explicación:
Subcuadrados {{2, 2}, {2, 2}} y {{3, 1}, {2, 2}} tienen suma 8.
Enfoque ingenuo:
el enfoque más simple para resolver el problema es generar todos los subcuadrados posibles y verificar la suma de todos los elementos del subcuadrado igual a X .
Complejidad Temporal: O(N 3 * M 3 )
Espacio Auxiliar: O(1), ya que no se ha tomado ningún espacio extra.
Enfoque eficiente: para optimizar el enfoque ingenuo anterior, se debe realizar la suma de todos los elementos de toda la array hasta cada celda. A continuación se muestran los pasos:
- Calcule previamente la suma de todos los rectángulos con la esquina superior izquierda en (0, 0) y la esquina inferior derecha en (i, j) en complejidad computacional O(N * M) .
- Ahora bien, se puede observar que, por cada esquina superior izquierda, puede haber como máximo un cuadrado con suma X ya que los elementos de la array son positivos.
- Teniendo esto en cuenta, podemos usar la búsqueda binaria para verificar si existe un cuadrado con suma X.
- Para cada celda (i, j) en la array, fíjela como la esquina superior izquierda del subcuadrado. Luego, recorra todos los subcuadrados posibles con (i, j) como la esquina superior izquierda y aumente la cuenta si la suma es igual a X o no.
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;
// Size of a column
#define m 5
// Function to find the count of submatrix
// whose sum is X
int countSubsquare(int arr[][m],
int n, int X)
{
int dp[n + 1][m + 1];
memset(dp, 0, sizeof(dp));
// Copying arr to dp and making
// it indexed 1
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
dp[i + 1][j + 1] = arr[i][j];
}
}
// Precalculate and store the sum
// of all rectangles with upper
// left corner at (0, 0);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// Calculating sum in
// a 2d grid
dp[i][j] += dp[i - 1][j]
+ dp[i][j - 1]
- dp[i - 1][j - 1];
}
}
// Stores the answer
int cnt = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// Fix upper left corner
// at {i, j} and perform
// binary search on all
// such possible squares
// Minimum length of square
int lo = 1;
// Maximum length of square
int hi = min(n - i, m - j) + 1;
// Flag to set if sub-square
// with sum X is found
bool found = false;
while (lo <= hi) {
int mid = (lo + hi) / 2;
// Calculate lower
// right index if upper
// right corner is at {i, j}
int ni = i + mid - 1;
int nj = j + mid - 1;
// Calculate the sum of
// elements in the submatrix
// with upper left column
// {i, j} and lower right
// column at {ni, nj};
int sum = dp[ni][nj]
- dp[ni][j - 1]
- dp[i - 1][nj]
+ dp[i - 1][j - 1];
if (sum >= X) {
// If sum X is found
if (sum == X) {
found = true;
}
hi = mid - 1;
// If sum > X, then size of
// the square with sum X
// must be less than mid
}
else {
// If sum < X, then size of
// the square with sum X
// must be greater than mid
lo = mid + 1;
}
}
// If found, increment
// count by 1;
if (found == true) {
cnt++;
}
}
}
return cnt;
}
// Driver Code
int main()
{
int N = 4, X = 10;
// Given Matrix arr[][]
int arr[N][m] = { { 2, 4, 3, 2, 10 },
{ 3, 1, 1, 1, 5 },
{ 1, 1, 2, 1, 4 },
{ 2, 1, 1, 1, 3 } };
// Function Call
cout << countSubsquare(arr, N, X)
<< endl;
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Size of a column
static final int m = 5;
// Function to find the count of submatrix
// whose sum is X
static int countSubsquare(int arr[][],
int n, int X)
{
int [][]dp = new int[n + 1][m + 1];
// Copying arr to dp and making
// it indexed 1
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
dp[i + 1][j + 1] = arr[i][j];
}
}
// Precalculate and store the sum
// of all rectangles with upper
// left corner at (0, 0);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
// Calculating sum in
// a 2d grid
dp[i][j] += dp[i - 1][j] +
dp[i][j - 1] -
dp[i - 1][j - 1];
}
}
// Stores the answer
int cnt = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
// Fix upper left corner
// at {i, j} and perform
// binary search on all
// such possible squares
// Minimum length of square
int lo = 1;
// Maximum length of square
int hi = Math.min(n - i, m - j) + 1;
// Flag to set if sub-square
// with sum X is found
boolean found = false;
while (lo <= hi)
{
int mid = (lo + hi) / 2;
// Calculate lower
// right index if upper
// right corner is at {i, j}
int ni = i + mid - 1;
int nj = j + mid - 1;
// Calculate the sum of
// elements in the submatrix
// with upper left column
// {i, j} and lower right
// column at {ni, nj};
int sum = dp[ni][nj] -
dp[ni][j - 1] -
dp[i - 1][nj] +
dp[i - 1][j - 1];
if (sum >= X)
{
// If sum X is found
if (sum == X)
{
found = true;
}
hi = mid - 1;
// If sum > X, then size of
// the square with sum X
// must be less than mid
}
else
{
// If sum < X, then size of
// the square with sum X
// must be greater than mid
lo = mid + 1;
}
}
// If found, increment
// count by 1;
if (found == true)
{
cnt++;
}
}
}
return cnt;
}
// Driver Code
public static void main(String[] args)
{
int N = 4, X = 10;
// Given Matrix arr[][]
int arr[][] = { { 2, 4, 3, 2, 10 },
{ 3, 1, 1, 1, 5 },
{ 1, 1, 2, 1, 4 },
{ 2, 1, 1, 1, 3 } };
// Function Call
System.out.print(countSubsquare(arr, N, X) + "\n");
}
}
// This code is contributed by sapnasingh4991
Python3
# Python3 program for the above approach
# Size of a column
m = 5
# Function to find the count of
# submatrix whose sum is X
def countSubsquare(arr, n, X):
dp = [[ 0 for x in range(m + 1)]
for y in range(n + 1)]
# Copying arr to dp and making
# it indexed 1
for i in range(n):
for j in range(m):
dp[i + 1][j + 1] = arr[i][j]
# Precalculate and store the sum
# of all rectangles with upper
# left corner at (0, 0);
for i in range(1, n + 1):
for j in range(1, m + 1):
# Calculating sum in
# a 2d grid
dp[i][j] += (dp[i - 1][j] +
dp[i][j - 1] -
dp[i - 1][j - 1])
# Stores the answer
cnt = 0
for i in range(1, n + 1):
for j in range(1, m + 1):
# Fix upper left corner
# at {i, j} and perform
# binary search on all
# such possible squares
# Minimum length of square
lo = 1
# Maximum length of square
hi = min(n - i, m - j) + 1
# Flag to set if sub-square
# with sum X is found
found = False
while (lo <= hi):
mid = (lo + hi) // 2
# Calculate lower right
# index if upper right
# corner is at {i, j}
ni = i + mid - 1
nj = j + mid - 1
# Calculate the sum of
# elements in the submatrix
# with upper left column
# {i, j} and lower right
# column at {ni, nj};
sum = (dp[ni][nj] -
dp[ni][j - 1] -
dp[i - 1][nj] +
dp[i - 1][j - 1])
if (sum >= X):
# If sum X is found
if (sum == X):
found = True
hi = mid - 1
# If sum > X, then size of
# the square with sum X
# must be less than mid
else:
# If sum < X, then size of
# the square with sum X
# must be greater than mid
lo = mid + 1
# If found, increment
# count by 1;
if (found == True):
cnt += 1
return cnt
# Driver Code
if __name__ =="__main__":
N, X = 4, 10
# Given matrix arr[][]
arr = [ [ 2, 4, 3, 2, 10 ],
[ 3, 1, 1, 1, 5 ],
[ 1, 1, 2, 1, 4 ],
[ 2, 1, 1, 1, 3 ] ]
# Function call
print(countSubsquare(arr, N, X))
# This code is contributed by chitranayal
C#
// C# program for the above approach
using System;
class GFG{
// Size of a column
static readonly int m = 5;
// Function to find the count of submatrix
// whose sum is X
static int countSubsquare(int [,]arr,
int n, int X)
{
int [,]dp = new int[n + 1, m + 1];
// Copying arr to dp and making
// it indexed 1
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
dp[i + 1, j + 1] = arr[i, j];
}
}
// Precalculate and store the sum
// of all rectangles with upper
// left corner at (0, 0);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
// Calculating sum in
// a 2d grid
dp[i, j] += dp[i - 1, j] +
dp[i, j - 1] -
dp[i - 1, j - 1];
}
}
// Stores the answer
int cnt = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
// Fix upper left corner
// at {i, j} and perform
// binary search on all
// such possible squares
// Minimum length of square
int lo = 1;
// Maximum length of square
int hi = Math.Min(n - i, m - j) + 1;
// Flag to set if sub-square
// with sum X is found
bool found = false;
while (lo <= hi)
{
int mid = (lo + hi) / 2;
// Calculate lower
// right index if upper
// right corner is at {i, j}
int ni = i + mid - 1;
int nj = j + mid - 1;
// Calculate the sum of
// elements in the submatrix
// with upper left column
// {i, j} and lower right
// column at {ni, nj};
int sum = dp[ni, nj] -
dp[ni, j - 1] -
dp[i - 1, nj] +
dp[i - 1, j - 1];
if (sum >= X)
{
// If sum X is found
if (sum == X)
{
found = true;
}
hi = mid - 1;
// If sum > X, then size of
// the square with sum X
// must be less than mid
}
else
{
// If sum < X, then size of
// the square with sum X
// must be greater than mid
lo = mid + 1;
}
}
// If found, increment
// count by 1;
if (found == true)
{
cnt++;
}
}
}
return cnt;
}
// Driver Code
public static void Main(String[] args)
{
int N = 4, X = 10;
// Given Matrix [,]arr
int [,]arr = { { 2, 4, 3, 2, 10 },
{ 3, 1, 1, 1, 5 },
{ 1, 1, 2, 1, 4 },
{ 2, 1, 1, 1, 3 } };
// Function call
Console.Write(countSubsquare(arr, N, X) + "\n");
}
}
// This code is contributed by amal kumar choubey
Javascript
<script>
// Javascript program for the above approach
// Size of a column
var m = 5;
// Function to find the count of submatrix
// whose sum is X
function countSubsquare(arr , n , X) {
var dp = Array(n + 1);
for(var i =0;i<n+1;i++)
dp[i] = Array(m + 1).fill(0);
// Copying arr to dp and making
// it indexed 1
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++) {
dp[i + 1][j + 1] = arr[i][j];
}
}
// Precalculate and store the sum
// of all rectangles with upper
// left corner at (0, 0);
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
// Calculating sum in
// a 2d grid
dp[i][j] += dp[i - 1][j] +
dp[i][j - 1] - dp[i - 1][j - 1];
}
}
// Stores the answer
var cnt = 0;
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
// Fix upper left corner
// at {i, j} and perform
// binary search on all
// such possible squares
// Minimum length of square
var lo = 1;
// Maximum length of square
var hi = Math.min(n - i, m - j) + 1;
// Flag to set if sub-square
// with sum X is found
var found = false;
while (lo <= hi) {
var mid = parseInt((lo + hi) / 2);
// Calculate lower
// right index if upper
// right corner is at {i, j}
var ni = i + mid - 1;
var nj = j + mid - 1;
// Calculate the sum of
// elements in the submatrix
// with upper left column
// {i, j} and lower right
// column at {ni, nj];
var sum = dp[ni][nj] - dp[ni][j - 1] -
dp[i - 1][nj] + dp[i - 1][j - 1];
if (sum >= X) {
// If sum X is found
if (sum == X) {
found = true;
}
hi = mid - 1;
// If sum > X, then size of
// the square with sum X
// must be less than mid
} else {
// If sum < X, then size of
// the square with sum X
// must be greater than mid
lo = mid + 1;
}
}
// If found, increment
// count by 1;
if (found == true) {
cnt++;
}
}
}
return cnt;
}
// Driver Code
var N = 4, X = 10;
// Given Matrix arr
var arr = [ [ 2, 4, 3, 2, 10 ],
[ 3, 1, 1, 1, 5 ],
[ 1, 1, 2, 1, 4 ],
[ 2, 1, 1, 1, 3 ] ];
// Function Call
document.write(countSubsquare(arr, N, X) + "<br/>");
// This code contributed by umadevi9616
</script>
Producción:
3
Complejidad de tiempo: O(N * M * log(max(N, M)))
Espacio auxiliar: O(N * M) ya que el espacio n*m se utiliza para poblar la array bidimensional dp.
Publicación traducida automáticamente
Artículo escrito por devanshuraj226 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA