Dada una array N x N y dos enteros S y K , la tarea es encontrar si existe una subarray K x K con suma igual a S .
Ejemplos:
Entrada: K = 2, S = 14, mat[][] = {
{ 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 }}
Salida: Sí
1 2
5 6
es la subarray 2 x 2 requerida con suma de elementos = 14Entrada: K = 1, S = 5, mat[][] = {{1, 2}, {7, 8}}
Salida: No
Enfoque: la programación dinámica se puede utilizar para resolver este problema,
- Cree una array dp[N + 1][N + 1] donde dp[ i ][j] almacena la suma de todos los elementos con una fila entre 1 y una columna entre 1 y j .
- Una vez que se genera la array 2-D, ahora supongamos que deseamos encontrar la suma de cuadrados que comienza con (i, j) hasta (i + x, j + x) . La suma requerida será dp[i + x][j + x] – dp[i][j + x] – dp[i + x][j] + dp[i][j] donde,
- El primer término denota la suma de todos los elementos presentes en filas entre 1 a i + x y columnas entre 1 a j + x . Esta área tiene nuestra plaza requerida.
- Los dos segundos términos son para eliminar el área que está fuera de nuestra región requerida pero dentro de la región calculada en el primer paso.
- La suma de los elementos de las filas entre 1 y i y las columnas entre 1 y j se resta dos veces en el segundo paso, por lo que se suma una vez.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define N 4
// Function to return the sum of the sub-matrix
int getSum(int r1, int r2, int c1, int c2,
int dp[N + 1][N + 1])
{
return dp[r2][c2] - dp[r2][c1] - dp[r1][c2]
+ dp[r1][c1];
}
// Function that returns true if it is possible
// to find the sub-matrix with required sum
bool sumFound(int K, int S, int grid[N][N])
{
// 2-D array to store the sum of
// all the sub-matrices
int dp[N + 1][N + 1];
// Filling of dp[][] array
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1]
- dp[i][j] + grid[i][j];
// Checking for each possible sub-matrix of size k X k
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
int sum = getSum(i, i + K, j, j + K, dp);
if (sum == S)
return true;
}
// Sub-matrix with the given sum not found
return false;
}
// Driver code
int main()
{
int grid[N][N] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
int K = 2;
int S = 14;
// Function call
if (sumFound(K, S, grid))
cout << "Yes" << endl;
else
cout << "No" << endl;
}
// Modified by Kartik Verma
Java
// Java implementation of the approach
class GfG {
static int N = 4;
// Function to return the sum of the sub-matrix
static int getSum(int r1, int r2, int c1, int c2,
int dp[][])
{
return dp[r2][c2] - dp[r2][c1] - dp[r1][c2]
+ dp[r1][c1];
}
// Function that returns true if it is possible
// to find the sub-matrix with required sum
static boolean sumFound(int K, int S, int grid[][])
{
// 2-D array to store the sum of
// all the sub-matrices
int dp[][] = new int[N + 1][N + 1];
// Filling of dp[][] array
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
dp[i + 1][j + 1] = dp[i + 1][j]
+ dp[i][j + 1] - dp[i][j]
+ grid[i][j];
}
}
// Checking for each possible sub-matrix of size k X
// k
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int sum = getSum(i, i + K, j, j + K, dp);
if (sum == S) {
return true;
}
}
}
// Sub-matrix with the given sum not found
return false;
}
// Driver code
public static void main(String[] args)
{
int grid[][] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
int K = 2;
int S = 14;
// Function call
if (sumFound(K, S, grid)) {
System.out.println("Yes");
}
else {
System.out.println("No");
}
}
}
// This code contributed by Rajput-Ji
// Modified by Kartik Verma
Python3
# Python implementation of the approach
N = 4
# Function to return the sum of the sub-matrix
def getSum(r1, r2, c1, c2, dp):
return dp[r2][c2] - dp[r2][c1] - dp[r1][c2] + dp[r1][c1]
# Function that returns true if it is possible
# to find the sub-matrix with required sum
def sumFound(K, S, grid):
# 2-D array to store the sum of
# all the sub-matrices
dp = [[0 for i in range(N+1)] for j in range(N+1)]
# Filling of dp[][] array
for i in range(N):
for j in range(N):
dp[i + 1][j + 1] = dp[i + 1][j] + \
dp[i][j + 1] - dp[i][j] + grid[i][j]
# Checking for each possible sub-matrix of size k X k
for i in range(0, N):
for j in range(0, N):
sum = getSum(i, i + K, j, j + K, dp)
if (sum == S):
return True
# Sub-matrix with the given sum not found
return False
# Driver code
grid = [[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]]
K = 2
S = 14
# Function call
if (sumFound(K, S, grid)):
print("Yes")
else:
print("No")
# This code is contributed by ankush_953
# Modified by Kartik Verma
C#
// C# implementation of the approach
using System;
class GfG {
static int N = 4;
// Function to return the sum of the sub-matrix
static int getSum(int r1, int r2, int c1, int c2,
int[, ] dp)
{
return dp[r2, c2] - dp[r2, c1] - dp[r1, c2]
+ dp[r1, c1];
}
// Function that returns true if it is possible
// to find the sub-matrix with required sum
static bool sumFound(int K, int S, int[, ] grid)
{
// 2-D array to store the sum of
// all the sub-matrices
int[, ] dp = new int[N + 1, N + 1];
// Filling of dp[,] array
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
dp[i + 1, j + 1] = dp[i + 1, j]
+ dp[i, j + 1] - dp[i, j]
+ grid[i, j];
}
}
// Checking for each possible sub-matrix of size k X
// k
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int sum = getSum(i, i + K, j, j + K, dp);
if (sum == S) {
return true;
}
}
}
// Sub-matrix with the given sum not found
return false;
}
// Driver code
public static void Main(String[] args)
{
int[, ] grid = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
int K = 2;
int S = 14;
// Function call
if (sumFound(K, S, grid)) {
Console.WriteLine("Yes");
}
else {
Console.WriteLine("No");
}
}
}
// This code has been contributed by 29AjayKumar
// Modified by Kartik Verma
PHP
<?php
// PHP implementation of the approach
$GLOBALS['N'] = 4;
// Function to return the sum of
// the sub-matrix
function getSum($r1, $r2, $c1, $c2, $dp)
{
return $dp[$r2][$c2] - $dp[$r2][$c1] -
$dp[$r1][$c2] + $dp[$r1][$c1];
}
// Function that returns true if it is
// possible to find the sub-matrix with
// required sum
function sumFound($K, $S, $grid)
{
// 2-D array to store the sum of
// all the sub-matrices
$dp = array(array());
for ($i = 0; $i < $GLOBALS['N']; $i++)
for ($j = 0; $j < $GLOBALS['N']; $j++)
$dp[$i][$j] = 0 ;
// Filling of dp[][] array
for ($i = 0; $i < $GLOBALS['N']; $i++)
for ($j = 0; $j < $GLOBALS['N']; $j++)
$dp[$i + 1][$j + 1] = $dp[$i + 1][$j] +
$dp[$i][$j + 1] -
$dp[$i][$j] +
$grid[$i][$j];
// Checking for each possible sub-matrix
// of size k X k
for ($i = 0;
$i < $GLOBALS['N']; $i++)
for ($j = 0;
$j < $GLOBALS['N']; $j++)
{
$sum = getSum($i, $i + $K, $j,
$j + $K, $dp);
if ($sum == $S)
return true;
}
// Sub-matrix with the given
// sum not found
return false;
}
// Driver code
$grid = array(array(1, 2, 3, 4),
array(5, 6, 7, 8),
array(9, 10, 11, 12),
array(13, 14, 15, 16));
$K = 2;
$S = 14;
// Function call
if (sumFound($K, $S, $grid))
echo "Yes";
else
echo "No";
// This code is contributed by Ryuga
//Modified by Kartik Verma
?>
Javascript
<script>
// Javascript implementation of the approach
var N = 4
// Function to return the sum of the sub-matrix
function getSum(r1, r2, c1, c2, dp)
{
return dp[r2][c2] - dp[r2][c1] - dp[r1][c2]
+ dp[r1][c1];
}
// Function that returns true if it is possible
// to find the sub-matrix with required sum
function sumFound(K, S, grid)
{
// 2-D array to store the sum of
// all the sub-matrices
var dp = Array.from(Array(N+1), ()=> Array(N+1).fill(0));
// Filling of dp[][] array
for (var i = 0; i < N; i++)
for (var j = 0; j < N; j++)
dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1]
- dp[i][j] + grid[i][j];
// Checking for each possible sub-matrix of size k X k
for (var i = 0; i < N; i++)
for (var j = 0; j < N; j++) {
var sum = getSum(i, i + K, j, j + K, dp);
if (sum == S)
return true;
}
// Sub-matrix with the given sum not found
return false;
}
// Driver code
var grid = [ [ 1, 2, 3, 4 ],
[ 5, 6, 7, 8 ],
[ 9, 10, 11, 12 ],
[ 13, 14, 15, 16 ] ];
var K = 2;
var S = 14;
// Function call
if (sumFound(K, S, grid))
document.write( "Yes");
else
document.write( "No" );
</script>
Producción:
Yes