Dada una array mat[][] y dos enteros K y S , la tarea es contar todas las subarray K x K de modo que la suma de todos los elementos de la subarray sea mayor o igual que S .
Ejemplos:
Input: K = 2, S = 15
mat[][] = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9}}
Output: 3
Explanation:
In the given matrix there are 3 sub-matrix
Sub-Matrix 1: (0, 1) to (1, 2)
Sum = 2 + 3 + 5 + 6 = 16
Sub-matrix 2: (1, 0) to (2, 1)
Sum = 4 + 5 + 7 + 8 = 24
Sub-matrix 3: (1, 1) to (2, 2)
Sum = 5 + 6 + 8 + 9 = 28
Input: K = 3, S = 35
arr[][] = {{1, 7, 1, 1, 1},
{2, 2, 2, 2, 2},
{3, 9, 6, 7, 3},
{4, 3, 2, 4, 5},
{5, 1, 5, 3, 1}}
Output: 5
Enfoque ingenuo: iterar sobre todas las posibles subarray de tamaño K x K y encontrar la suma de cada array. Si la suma de cualquier subarray es mayor que la suma S dada , incremente el conteo en 1.
Enfoque eficiente: la idea es calcular previamente la suma del prefijo de la array de modo que la suma de cada suma de subarray se pueda calcular en tiempo O(1). Finalmente, itere sobre todas las posiciones posibles de la array y verifique la suma de la subarray de tamaño K x K de esas posiciones con el principio de inclusión y exclusión . Si la suma es mayor que la suma dada, incremente el recuento de dicha subarray en 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count total number
// of k x k sub matrix whose sum is
// greater than the given number S
#include <iostream>
using namespace std;
#define dim 5
// Function to create Prefix sum
// matrix from the given matrix
void createTable(int mtrx[][dim],
int k, int p, int dp[][dim])
{
// Store first value in table
dp[0][0] = mtrx[0][0];
// Initialize first row of matrix
for (int j = 1; j < dim; j++) {
dp[0][j] = mtrx[0][j] +
dp[0][j - 1];
}
// Initialize first column of matrix
for (int i = 1; i < dim; i++) {
dp[i][0] = mtrx[i][0] +
dp[i - 1][0];
}
// Initialize rest table with sum
for (int i = 1; i < dim; i++) {
for (int j = 1; j < dim; j++) {
dp[i][j] = mtrx[i][j] +
dp[i - 1][j] + dp[i][j - 1] -
dp[i - 1][j - 1];
}
}
}
// Utility Function to count the submatrix
// whose sum is greater than the S
int countSubMatrixUtil(int dp[][dim],
int k, int p)
{
int count = 0;
int subMatSum = 0;
// Loop to iterate over all the
// possible positions of the
// given matrix mat[][]
for (int i = k - 1; i < dim; i++) {
for (int j = k - 1; j < dim;
j++) {
if (i == (k - 1) || j == (k - 1)) {
// Condition to check, if K x K
// is first sub matrix
if (i == (k - 1) && j == (k - 1)) {
subMatSum = dp[i][j];
}
// Condition to check sub-matrix
// has no margin at top
else if (i == (k - 1)) {
subMatSum = dp[i][j] - dp[i][j - k];
}
// Condition when sub matrix
// has no margin at left
else {
subMatSum = dp[i][j] - dp[i - k][j];
}
}
// Condition when submatrix has
// margin at top and left
else {
subMatSum = dp[i][j] - dp[i - k][j] -
dp[i][j - k] + dp[i - k][j - k];
}
// Increment count, If sub matrix
// sum is greater than S
if (subMatSum >= p) {
count++;
}
}
}
return count;
}
// Function to count submatrix of
// size k x k such that sum if
// greater than or equal to S
int countSubMatrix(int mtrx[][dim], int k, int p)
{
int dp[dim][dim];
// For loop to initialize prefix sum
// matrix with zero, initially
for (int i = 0; i < dim; i++) {
for (int j = 0; j < dim; j++) {
dp[i][j] = 0;
}
}
// Function to create the
// prefix sum matrix
createTable(mtrx, k, p, dp);
return countSubMatrixUtil(dp, k, p);
}
// Driver Code
int main()
{
int mtrx[dim][dim] = {
{ 1, 7, 1, 1, 1 },
{ 2, 2, 2, 2, 2 },
{ 3, 9, 6, 7, 3 },
{ 4, 3, 2, 4, 5 },
{ 5, 1, 5, 3, 1 }
};
int k = 3;
int p = 35;
// Print total number of sub matrix
cout << countSubMatrix(mtrx, k, p);
return 0;
}
Java
// Java program to count total number
// of k x k sub matrix whose sum is
// greater than the given number S
import java.util.*;
class GFG{
static final int dim = 5;
// Function to create prefix sum
// matrix from the given matrix
static void createTable(int mtrx[][],
int k, int p,
int dp[][])
{
// Store first value in table
dp[0][0] = mtrx[0][0];
// Initialize first row of matrix
for(int j = 1; j < dim; j++)
{
dp[0][j] = mtrx[0][j] +
dp[0][j - 1];
}
// Initialize first column of matrix
for(int i = 1; i < dim; i++)
{
dp[i][0] = mtrx[i][0] +
dp[i - 1][0];
}
// Initialize rest table with sum
for(int i = 1; i < dim; i++)
{
for(int j = 1; j < dim; j++)
{
dp[i][j] = mtrx[i][j] +
dp[i - 1][j] +
dp[i][j - 1] -
dp[i - 1][j - 1];
}
}
}
// Utility Function to count the submatrix
// whose sum is greater than the S
static int countSubMatrixUtil(int dp[][],
int k, int p)
{
int count = 0;
int subMatSum = 0;
// Loop to iterate over all the
// possible positions of the
// given matrix mat[][]
for(int i = k - 1; i < dim; i++)
{
for(int j = k - 1; j < dim; j++)
{
if (i == (k - 1) || j == (k - 1))
{
// Condition to check, if K x K
// is first sub matrix
if (i == (k - 1) && j == (k - 1))
{
subMatSum = dp[i][j];
}
// Condition to check sub-matrix
// has no margin at top
else if (i == (k - 1))
{
subMatSum = dp[i][j] -
dp[i][j - k];
}
// Condition when sub matrix
// has no margin at left
else
{
subMatSum = dp[i][j] -
dp[i - k][j];
}
}
// Condition when submatrix has
// margin at top and left
else
{
subMatSum = dp[i][j] - dp[i - k][j] -
dp[i][j - k] +
dp[i - k][j - k];
}
// Increment count, If sub matrix
// sum is greater than S
if (subMatSum >= p)
{
count++;
}
}
}
return count;
}
// Function to count submatrix of
// size k x k such that sum if
// greater than or equal to S
static int countSubMatrix(int mtrx[][],
int k, int p)
{
int [][]dp = new int[dim][dim];
// For loop to initialize prefix sum
// matrix with zero, initially
for(int i = 0; i < dim; i++)
{
for(int j = 0; j < dim; j++)
{
dp[i][j] = 0;
}
}
// Function to create the
// prefix sum matrix
createTable(mtrx, k, p, dp);
return countSubMatrixUtil(dp, k, p);
}
// Driver Code
public static void main(String[] args)
{
int mtrx[][] = { { 1, 7, 1, 1, 1 },
{ 2, 2, 2, 2, 2 },
{ 3, 9, 6, 7, 3 },
{ 4, 3, 2, 4, 5 },
{ 5, 1, 5, 3, 1 } };
int k = 3;
int p = 35;
// Print total number of sub matrix
System.out.print(countSubMatrix(mtrx, k, p));
}
}
// This code is contributed by Rohit_ranjan
Python3
# Python3 program to count total number # of k x k sub matrix whose sum is # greater than the given number S dim = 5 # Function to create prefix sum # matrix from the given matrix def createTable(mtrx, k, p, dp): # Store first value in table dp[0][0] = mtrx[0][0] # Initialize first row of matrix for j in range(1, dim): dp[0][j] = mtrx[0][j] + dp[0][j - 1] # Initialize first column of matrix for i in range(1, dim): dp[i][0] = mtrx[i][0] + dp[i - 1][0] # Initialize rest table with sum for i in range(1, dim): for j in range(1, dim): dp[i][j] = (mtrx[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]) # Utility function to count the submatrix # whose sum is greater than the S def countSubMatrixUtil(dp, k, p): count = 0 subMatSum = 0 # Loop to iterate over all the # possible positions of the # given matrix mat[][] for i in range(k - 1, dim): for j in range(k - 1, dim, 1): if (i == (k - 1) or j == (k - 1)): # Condition to check, if K x K # is first sub matrix if (i == (k - 1) and j == (k - 1)): subMatSum = dp[i][j] # Condition to check sub-matrix # has no margin at top elif (i == (k - 1)): subMatSum = dp[i][j] - dp[i][j - k] # Condition when sub matrix # has no margin at left else: subMatSum = dp[i][j] - dp[i - k][j] # Condition when submatrix has # margin at top and left else: subMatSum = (dp[i][j] - dp[i - k][j] - dp[i][j - k] + dp[i - k][j - k]) # Increment count, If sub matrix # sum is greater than S if (subMatSum >= p): count += 1 return count # Function to count submatrix of # size k x k such that sum if # greater than or equal to S def countSubMatrix(mtrx, k, p): dp = [[0 for i in range(dim)] for j in range(dim)] # For loop to initialize prefix sum # matrix with zero, initially for i in range(dim): for j in range(dim): dp[i][j] = 0 # Function to create the # prefix sum matrix createTable(mtrx, k, p, dp) return countSubMatrixUtil(dp, k, p) # Driver Code if __name__ == '__main__': mtrx = [ [ 1, 7, 1, 1, 1 ], [ 2, 2, 2, 2, 2 ], [ 3, 9, 6, 7, 3 ], [ 4, 3, 2, 4, 5 ], [ 5, 1, 5, 3, 1 ] ] k = 3 p = 35 # Print total number of sub matrix print(countSubMatrix(mtrx, k, p)) # This code is contributed by Bhupendra_Singh
C#
// C# program to count total number
// of k x k sub matrix whose sum is
// greater than the given number S
using System;
class GFG{
static readonly int dim = 5;
// Function to create prefix sum
// matrix from the given matrix
static void createTable(int [,]mtrx,
int k, int p,
int [,]dp)
{
// Store first value in table
dp[0, 0] = mtrx[0, 0];
// Initialize first row of matrix
for(int j = 1; j < dim; j++)
{
dp[0, j] = mtrx[0, j] +
dp[0, j - 1];
}
// Initialize first column of matrix
for(int i = 1; i < dim; i++)
{
dp[i, 0] = mtrx[i, 0] +
dp[i - 1, 0];
}
// Initialize rest table with sum
for(int i = 1; i < dim; i++)
{
for(int j = 1; j < dim; j++)
{
dp[i, j] = mtrx[i, j] +
dp[i - 1, j] +
dp[i, j - 1] -
dp[i - 1, j - 1];
}
}
}
// Utility Function to count the submatrix
// whose sum is greater than the S
static int countSubMatrixUtil(int [,]dp,
int k, int p)
{
int count = 0;
int subMatSum = 0;
// Loop to iterate over all the
// possible positions of the
// given matrix [,]mat
for(int i = k - 1; i < dim; i++)
{
for(int j = k - 1; j < dim; j++)
{
if (i == (k - 1) || j == (k - 1))
{
// Condition to check, if K x K
// is first sub matrix
if (i == (k - 1) && j == (k - 1))
{
subMatSum = dp[i, j];
}
// Condition to check sub-matrix
// has no margin at top
else if (i == (k - 1))
{
subMatSum = dp[i, j] -
dp[i, j - k];
}
// Condition when sub matrix
// has no margin at left
else
{
subMatSum = dp[i, j] -
dp[i - k, j];
}
}
// Condition when submatrix has
// margin at top and left
else
{
subMatSum = dp[i, j] - dp[i - k, j] -
dp[i, j - k] +
dp[i - k, j - k];
}
// Increment count, If sub matrix
// sum is greater than S
if (subMatSum >= p)
{
count++;
}
}
}
return count;
}
// Function to count submatrix of
// size k x k such that sum if
// greater than or equal to S
static int countSubMatrix(int [,]mtrx,
int k, int p)
{
int [,]dp = new int[dim, dim];
// For loop to initialize prefix sum
// matrix with zero, initially
for(int i = 0; i < dim; i++)
{
for(int j = 0; j < dim; j++)
{
dp[i, j] = 0;
}
}
// Function to create the
// prefix sum matrix
createTable(mtrx, k, p, dp);
return countSubMatrixUtil(dp, k, p);
}
// Driver Code
public static void Main(String[] args)
{
int [,]mtrx = { { 1, 7, 1, 1, 1 },
{ 2, 2, 2, 2, 2 },
{ 3, 9, 6, 7, 3 },
{ 4, 3, 2, 4, 5 },
{ 5, 1, 5, 3, 1 } };
int k = 3;
int p = 35;
// Print total number of sub matrix
Console.Write(countSubMatrix(mtrx, k, p));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to count total number
// of k x k sub matrix whose sum is
// greater than the given number S
var dim = 5;
// Function to create Prefix sum
// matrix from the given matrix
function createTable(mtrx, k, p, dp)
{
// Store first value in table
dp[0][0] = mtrx[0][0];
// Initialize first row of matrix
for (var j = 1; j < dim; j++) {
dp[0][j] = mtrx[0][j] +
dp[0][j - 1];
}
// Initialize first column of matrix
for (var i = 1; i < dim; i++) {
dp[i][0] = mtrx[i][0] +
dp[i - 1][0];
}
// Initialize rest table with sum
for (var i = 1; i < dim; i++) {
for (var j = 1; j < dim; j++) {
dp[i][j] = mtrx[i][j] +
dp[i - 1][j] + dp[i][j - 1] -
dp[i - 1][j - 1];
}
}
}
// Utility Function to count the submatrix
// whose sum is greater than the S
function countSubMatrixUtil(dp, k, p)
{
var count = 0;
var subMatSum = 0;
// Loop to iterate over all the
// possible positions of the
// given matrix mat[][]
for (var i = k - 1; i < dim; i++) {
for (var j = k - 1; j < dim;
j++) {
if (i == (k - 1) || j == (k - 1)) {
// Condition to check, if K x K
// is first sub matrix
if (i == (k - 1) && j == (k - 1)) {
subMatSum = dp[i][j];
}
// Condition to check sub-matrix
// has no margin at top
else if (i == (k - 1)) {
subMatSum = dp[i][j] - dp[i][j - k];
}
// Condition when sub matrix
// has no margin at left
else {
subMatSum = dp[i][j] - dp[i - k][j];
}
}
// Condition when submatrix has
// margin at top and left
else {
subMatSum = dp[i][j] - dp[i - k][j] -
dp[i][j - k] + dp[i - k][j - k];
}
// Increment count, If sub matrix
// sum is greater than S
if (subMatSum >= p) {
count++;
}
}
}
return count;
}
// Function to count submatrix of
// size k x k such that sum if
// greater than or equal to S
function countSubMatrix(mtrx, k, p)
{
var dp = Array.from(Array(dim), ()=>Array(dim));
// For loop to initialize prefix sum
// matrix with zero, initially
for (var i = 0; i < dim; i++) {
for (var j = 0; j < dim; j++) {
dp[i][j] = 0;
}
}
// Function to create the
// prefix sum matrix
createTable(mtrx, k, p, dp);
return countSubMatrixUtil(dp, k, p);
}
// Driver Code
var mtrx = [
[ 1, 7, 1, 1, 1 ],
[ 2, 2, 2, 2, 2 ],
[ 3, 9, 6, 7, 3 ],
[ 4, 3, 2, 4, 5 ],
[ 5, 1, 5, 3, 1 ]
];
var k = 3;
var p = 35;
// Print total number of sub matrix
document.write( countSubMatrix(mtrx, k, p));
</script>
Producción:
5
Complejidad de Tiempo: O(M * N)
Espacio Auxiliar: O(M * N)
Publicación traducida automáticamente
Artículo escrito por MohammadMudassir y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA