Dada una array 2D de tamaño N x M y Q consultas donde cada consulta representa una coordenada (x, y) de la array, la tarea es encontrar la suma de todos los elementos que se encuentran en las diagonales que pasan por el punto dado.
Ejemplos:
Entrada: N = 4, M = 4, mat[][] = {{1, 2, 2, 1}, {2, 4, 2, 4}, {2, 2, 3, 1}, {2, 4, 2, 4}}, consulta = { {0, 0}, {3, 1}, {3, 3} }
Salida: 12, 13, 12
Explicación:
para la consulta 1, la suma de todos los elementos diagonales desde ( 0, 0) es 1 + 4 + 3 + 4 = 12
Para la consulta 2, la suma de todos los elementos diagonales de (3, 1) es 2 + 4 + 3 + 4 = 13
Para la consulta 3, la suma de todos los elementos diagonales de (3, 3) es 4 + 3 + 4 + 1 = 12Entrada: N = 3, M = 4, mat[][] = {{1, 0, 1}, {0, 1, 1}, {1, 1, 0}}, consulta = {{1, 1} , {2, 1}}
Salida: 4, 2
Enfoque ingenuo: la manera simple de resolver el problema es la siguiente:
- Para cada consulta, ejecute un bucle para calcular la suma de la diagonal inclinada a la izquierda que pasa por (x, y).
- Ejecute otro bucle para calcular la suma de la diagonal inclinada a la derecha que pasa por (x, y).
- En el cálculo de estas dos diagonales laterales, contamos (x, y) dos veces. Así que ahora resta eso de la suma de ambas sumas diagonales.
Complejidad de Tiempo: O(Q * N * M)
Espacio Auxiliar: O(1)
Enfoque eficiente: el problema se puede resolver de manera eficiente con base en la siguiente idea:
Calcule previamente las sumas diagonales inclinadas a la izquierda y a la derecha y guárdelas de tal manera que se pueda acceder y utilizar fácilmente para todos los valores de (x, y)
En cualquier array de tamaño N x M, el número total de diagonales inclinadas a la izquierda o diagonales inclinadas a la derecha es siempre N + M – 1 . Así que crea dos vectores de tamaño (N + M – 1) para almacenar la suma de cada tipo particular de diagonal en el vector respectivo.
El valor de (i+j) a lo largo de las diagonales inclinadas a la derecha es igual y (N-i+j-1) a lo largo de las diagonales inclinadas a la izquierda son iguales. Entonces, estos valores se pueden usar como índices para almacenar la suma de esa diagonal.
Ilustraciones:
En esta array de 3 x 4 :
1 2 3 4
________________1 | Un 00 Un 01 Un 02 Un 03
2 | 10 11 12 13 _ _ _ _
3 | 20 21 22 23 _ _ _ _
- Para (1, 1) La salida será (A 00 + A 11 + A 22 + A 20 + A 02 ).
- Para (2, 1) La salida será (A 10 + A 21 + A 12 + A 03 )
- Para diagonales inclinadas a la derecha
- Comience desde la parte superior izquierda y siga cubriendo todas las diagonales hasta la parte inferior derecha.
- De acuerdo con la ilustración anterior, la i-ésima diagonal inclinada a la derecha contiene los siguientes elementos
- 0ª diagonal = A 00
- 1ra diagonal = A 10 + A 01
- 2da diagonal = A 20 + A 11 + A 02
- 3ra diagonal = A 21 + A 12 + A 03
- 4ta diagonal = A 22 + A 13
- 5ª diagonal = A 23
- Almacenar los valores anteriores en el vector right_inclined_digsum en el mismo orden.
- Para verificar el elemento (x, y) que pertenece a qué diagonal, solo observe que A ij pertenece a (i + j) la diagonal inclinada a la derecha.
- Para diagonales inclinadas a la izquierda
- Comience desde la parte inferior izquierda y siga cubriendo todas las diagonales hasta la parte superior derecha
- De acuerdo con la ilustración anterior, la i-ésima diagonal inclinada a la izquierda contiene los siguientes elementos
- 0ª diagonal = A 20
- 1ra diagonal = A 10 + A 21
- 2da diagonal = A 00 + A 11 + A 22
- 3ra diagonal = A 01 + A 12 + A 23
- 4ta diagonal = A 02 + A 13
- 5ª diagonal = A 03
- Almacenar los valores anteriores en el vector left_inclined_digsum en el mismo orden.
- Para comprobar a qué diagonal pertenece el elemento (x, y), observe que A ij pertenece a (N – i + j – 1) la diagonal inclinada a la izquierda.
- Después de calcular previamente todos estos datos, para cada consulta de salida (x, y)
- suma_inclinada_derecha[x + y] + suma_inclinada_izquierda[N – x + y – 1] – arr[x][y]
Siga los pasos mencionados a continuación para implementar la idea:
- Cree dos vectores para almacenar las sumas diagonales (uno para inclinado a la izquierda y otro para inclinado a la derecha).
- Almacene la suma de las diagonales en los índices como se muestra arriba.
- Encuentre las diagonales de las que forma parte la coordenada actual.
- Calcule la suma como se muestra arriba.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
const int n = 4;
const int m = 4;
// Function for diagonal sum
int diagonal_sum(vector<vector<int> >& arr,
vector<int>& right_inclined_digsum,
vector<int>& left_inclined_digsum, int n,
int x, int y)
{
// To make it compatible with 0 based indexing
int a = (n - x) + y - 1;
int b = x + y;
int sum = right_inclined_digsum[b]
+ left_inclined_digsum[a] - arr[x][y];
return sum;
}
// Precomputaion
void precompute(int n, int m, vector<vector<int> > arr,
vector<int>& right_inclined_digsum,
vector<int>& left_inclined_digsum)
{
// To cover all diagonals of (/) type
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
right_inclined_digsum[i + j] += arr[i][j];
}
}
// To cover all diagonals of (\) type
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < m; j++) {
left_inclined_digsum[n - 1 - i + j]
+= arr[i][j];
}
// precomputaion done
}
}
void solve(vector<vector<int> >& arr, int Q,
vector<pair<int, int> >& query)
{
vector<int> right_inclined_digsum(n + m - 1, 0);
vector<int> left_inclined_digsum(n + m - 1, 0);
// Function for precomputation
precompute(n, m, arr, right_inclined_digsum,
left_inclined_digsum);
// Iterator for these coordinates
int it = 0;
while (Q--) {
int x = query[it].first;
int y = query[it].second;
cout << diagonal_sum(arr, right_inclined_digsum,
left_inclined_digsum, n, x, y)
<< "\n";
it++;
}
}
// Drivers code
int main()
{
vector<vector<int> > arr = { { 1, 2, 2, 1 },
{ 2, 4, 2, 4 },
{ 2, 2, 3, 1 },
{ 2, 4, 2, 4 } };
int Q = 3;
// Defining coordinates for each query
vector<pair<int, int> > query;
query.push_back({ 0, 0 });
query.push_back({ 3, 1 });
query.push_back({ 3, 3 });
// Function call
solve(arr, Q, query);
return 0;
}
Java
// Java code to implement the approach
import java.io.*;
import java.util.*;
class GFG {
static int n = 4;
static int m = 4;
// Function for diagonal sum
static int diagonal_sum(int[][] arr,
int[] right_inclined_digsum,
int[] left_inclined_digsum,
int n, int x, int y)
{
// To make it compatible with 0 based indexing
int a = (n - x) + y - 1;
int b = x + y;
int sum = right_inclined_digsum[b]
+ left_inclined_digsum[a] - arr[x][y];
return sum;
}
// Precomputaion
static void precompute(int n, int m, int[][] arr,
int[] right_inclined_digsum,
int[] left_inclined_digsum)
{
// To cover all diagonals of (/) type
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
right_inclined_digsum[i + j] += arr[i][j];
}
}
// To cover all diagonals of (\) type
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < m; j++) {
left_inclined_digsum[n - 1 - i + j]
+= arr[i][j];
}
// precomputaion done
}
}
static void solve(int[][] arr, int Q, int[][] query)
{
int[] right_inclined_digsum = new int[n + m - 1];
int[] left_inclined_digsum = new int[n + m - 1];
// Function for precomputation
precompute(n, m, arr, right_inclined_digsum,
left_inclined_digsum);
// Iterator for these coordinates
int it = 0;
while (Q-- > 0) {
int x = query[it][0];
int y = query[it][1];
System.out.println(diagonal_sum(
arr, right_inclined_digsum,
left_inclined_digsum, n, x, y));
it++;
}
}
// Driver code
public static void main(String[] args)
{
int[][] arr = { { 1, 2, 2, 1 },
{ 2, 4, 2, 4 },
{ 2, 2, 3, 1 },
{ 2, 4, 2, 4 } };
int Q = 3;
// Defining coordinates for each query
int[][] query = new int[3][2];
query[0] = new int[] { 0, 0 };
query[1] = new int[] { 3, 1 };
query[2] = new int[] { 3, 3 };
// Function call
solve(arr, Q, query);
}
}
// This code is contributed by Karandeep1234
Python3
# Python code for the above approach n = 4 m = 4 right_inclined_digsum = [0]*(n+m-1) left_inclined_digsum = [0]*(n+m-1) # Function for diagonal sum def diagonal_sum(arr, right_inclined_digsum, left_inclined_digsum, n, x, y): # To make it compatible with 0 based indexing a = (n-x)+y-1 b = x+y summ = right_inclined_digsum[b]+left_inclined_digsum[a]-arr[x][y] return summ # Precomputaion function def precompute(n, m, arr, right_inclined_digsum, left_inclined_digsum): # To cover all diagonals of (/) type for i in range(n): for j in range(m): right_inclined_digsum[i+j] += arr[i][j] # To cover all diagonals of (\) type for i in range(n-1, -1, -1): for j in range(0, m): left_inclined_digsum[n-1-i+j] += arr[i][j] # precomputaion done def solve(arr, Q, query): # Function for precomputation precompute(n, m, arr, right_inclined_digsum, left_inclined_digsum) # Iterator for these coordinates it = 0 while(Q > 0): x = query[it][0] y = query[it][1] print(diagonal_sum(arr, right_inclined_digsum, left_inclined_digsum, n, x, y)) it += 1 Q -= 1 # Drivers code if __name__ == "__main__": arr = [[1, 2, 2, 1], [2, 4, 2, 4], [2, 2, 3, 1], [2, 4, 2, 4]] Q = 3 # Defining coordinates for each query query = [] query.append([0, 0]) query.append([3, 1]) query.append([3, 3]) # Function call solve(arr, Q, query) " Code is written by RAJAT KUMAR [GLAU] "
C#
// C# code for the above approach:
using System;
using System.Collections.Generic;
class pair {
public int first, second;
public pair(int x, int y)
{
this.first = x;
this.second = y;
}
}
class GFG {
static int n = 4;
static int m = 4;
// Function for diagonal sum
static int diagonal_sum(int[, ] arr,
List<int> right_inclined_digsum,
List<int> left_inclined_digsum,
int n, int x, int y)
{
// To make it compatible with 0 based indexing
int a = (n - x) + y - 1;
int b = x + y;
int sum = right_inclined_digsum[b]
+ left_inclined_digsum[a] - arr[x, y];
return sum;
}
// Precomputaion
static void precompute(int n, int m, int[, ] arr,
List<int> right_inclined_digsum,
List<int> left_inclined_digsum)
{
// To cover all diagonals of (/) type
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
right_inclined_digsum[i + j] += arr[i, j];
}
}
// To cover all diagonals of (\) type
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < m; j++) {
left_inclined_digsum[n - 1 - i + j]
+= arr[i, j];
}
// precomputaion done
}
}
static void solve(int[, ] arr, int Q, List<pair> query)
{
List<int> right_inclined_digsum = new List<int>();
List<int> left_inclined_digsum = new List<int>();
for (int i = 0; i < n + m - 1; i++) {
right_inclined_digsum.Add(0);
left_inclined_digsum.Add(0);
}
// Function for precomputation
precompute(n, m, arr, right_inclined_digsum,
left_inclined_digsum);
// Iterator for these coordinates
int it = 0;
while (Q > 0) {
Q--;
int x = query[it].first;
int y = query[it].second;
Console.WriteLine(diagonal_sum(
arr, right_inclined_digsum,
left_inclined_digsum, n, x, y));
it++;
}
}
// Drivers code
public static void Main(string[] args)
{
int[, ] arr = { { 1, 2, 2, 1 },
{ 2, 4, 2, 4 },
{ 2, 2, 3, 1 },
{ 2, 4, 2, 4 } };
int Q = 3;
// Defining coordinates for each query
List<pair> query = new List<pair>();
query.Add(new pair(0, 0));
query.Add(new pair(3, 1));
query.Add(new pair(3, 3));
// Function call
solve(arr, Q, query);
}
}
// This code is contributed by phasing17
Javascript
<script>
// JavaScript code for the above approach
let n = 4;
let m = 4;
let right_inclined_digsum = new Array(n + m - 1).fill(0);
let left_inclined_digsum = new Array(n + m - 1).fill(0);
// Function for diagonal sum
function diagonal_sum(arr,
right_inclined_digsum,
left_inclined_digsum, n,
x, y)
{
// To make it compatible with 0 based indexing
let a = (n - x) + y - 1;
let b = x + y;
let sum = right_inclined_digsum[b]
+ left_inclined_digsum[a] - arr[x][y];
return sum;
}
// Precomputaion
function precompute(n, m, arr,
right_inclined_digsum,
left_inclined_digsum) {
// To cover all diagonals of (/) type
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
right_inclined_digsum[i + j] += arr[i][j];
}
}
// To cover all diagonals of (\) type
for (let i = n - 1; i >= 0; i--) {
for (let j = 0; j < m; j++) {
left_inclined_digsum[n - 1 - i + j]
+= arr[i][j];
}
// precomputaion done
}
}
function solve(arr, Q, query)
{
// Function for precomputation
precompute(n, m, arr, right_inclined_digsum,
left_inclined_digsum);
// Iterator for these coordinates
let it = 0;
while (Q--) {
let x = query[it][0];
let y = query[it][1];
document.write(diagonal_sum(arr, right_inclined_digsum,
left_inclined_digsum, n, x, y)
+ '</br>');
it++;
}
}
// Drivers code
let arr = [[1, 2, 2, 1],
[2, 4, 2, 4],
[2, 2, 3, 1],
[2, 4, 2, 4]];
let Q = 3;
// Defining coordinates for each query
let query = [];
query.push([0, 0]);
query.push([3, 1]);
query.push([3, 3]);
// Function call
solve(arr, Q, query);
// This code is contributed by Potta Lokesh
</script>
Producción
12 13 12
Complejidad temporal: O(Q + N * M)
Espacio auxiliar: O(N + M)
Publicación traducida automáticamente
Artículo escrito por refertoyash y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA