Dada una array A[][] de tamaño N * M y una array 2D queries[][] que consta de Q consultas de la forma {L, R} , la tarea es contar el número de sumas de filas y sumas de columnas que son un número entero del rango [L, R] .
Ejemplos:
Entrada: N = 2, M = 2, A[][] = {{1, 4}, {2, 5}}, Q = 2, consultas[][] = {{3, 7}, {3, 9}}
Salida: 3 4
Explicación:
Suma de la primera fila = 1 + 4 = 5.
Suma de la segunda fila = 2 + 5 = 7.
Suma de la primera columna = 1 + 2 = 3.
Suma de la segunda columna = 4 + 5 = 9.Consulta 1: L = 3, R = 7:
Suma de columna presente en el rango = 3. Suma de
fila presente en el rango = {5, 7}.
Por lo tanto, la cuenta es 3.
Consulta 2: L = 3, R = 9:
suma de columna presente en el rango = {3, 9}.
Sumas de fila presentes en el rango = {5, 7}.
Por lo tanto, la cuenta es 4.Entrada: N = 3, M = 2, A[][] = {{13, 3}, {9, 4}, {6, 10}}, Q = 2, consultas[][] = {{10, 20}, {25, 35}}
Salida: 4 1
Enfoque eficiente : la idea es recorrer la array en filas y columnas y precalcular la suma de cada fila y columna respectivamente. Recorra la array consultas[][] y cuente el número de sumas de filas o sumas de columnas presentes en los rangos dados usando Binary Search . Siga los pasos a continuación para resolver el problema:
- Inicialice dos arrays auxiliares , digamos row_sum[] & col_sum[] , para almacenar la suma de filas y columnas.
- Inicialice otra array, digamos sum_list[], para almacenar todos los elementos de sumas de filas y sumas de columnas combinados.
- Ordene la array sum_list[] en orden ascendente .
- Recorra las consultas de array [] y para cada consulta:
- Realice una búsqueda binaria para encontrar el índice, digamos i, de la suma más a la izquierda, es decir, L.
- Nuevamente, realice una búsqueda binaria para encontrar el índice j de la suma más a la derecha, es decir, R
- Imprime j – i + 1 como el resultado de la consulta.
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 search for the
// leftmost index of given number
int left_search(vector<int> A, int num)
{
// Initialize low, high and ans
int low = 0, high = A.size() - 1;
int ans = 0;
while (low <= high)
{
// Stores mid
int mid = low + (high - low) / 2;
// If A[mid] >= num
if (A[mid] >= num)
{
ans = mid;
high = mid - 1;
}
else
{
low = mid + 1;
}
}
return ans;
}
// Function to search for the
// rightmost index of given number
int right_search(vector<int> A, int num)
{
// Initialise low, high and ans
int low = 0, high = A.size() - 1;
int ans = high;
while (low <= high)
{
// Stores mid
int mid = low + (high - low) / 2;
// If A[mid] <= num
if (A[mid] <= num)
{
// Update ans
ans = mid;
// Update mid
low = mid + 1;
}
else
{
// Update high
high = mid - 1;
}
}
return ans;
}
// Function to preprocess the matrix to execute the
// queries
void totalCount(vector<vector<int>> A, int N, int M, vector<vector<int>> queries, int Q)
{
// Stores the sum of each row
vector<int> row_sum(N);
// Stores the sum of each col
vector<int> col_sum(N);
// Traverse the matrix and calculate
// sum of each row and column
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
row_sum[i] += A[i][j];
col_sum[j] += A[i][j];
}
}
vector<int> sum_list;
// Insert all row sums in sum_list
for (int i = 0; i < N; i++)
sum_list.push_back(row_sum[i]);
// Insert all column sums in sum_list
for (int i = 0; i < M; i++)
sum_list.push_back(col_sum[i]);
// Sort the array in ascending order
sort(sum_list.begin(), sum_list.end());
// Traverse the array queries[][]
for (int i = 0; i < Q; i++)
{
int L = queries[i][0];
int R = queries[i][1];
// Search the leftmost index of L
int l = left_search(sum_list, L);
// Search the rightmost index of R
int r = right_search(sum_list, R);
cout << r - l + 1 << " ";
}
}
// Driver Code
int main()
{
// Given dimensions of matrix
int N = 3, M = 2;
// Given matrix
vector<vector<int>> A = {{13, 3},
{9, 4},
{6, 10}};
// Given number of queries
int Q = 2;
// Given queries
vector<vector<int>> queries = {{10, 20}, {25, 35}};
// Function call to count the
// number row-sums and column-sums
// present in the given ranges
totalCount(A, N, M, queries, Q);
}
// This code is contributed by nirajgusain5
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to preprocess the matrix to execute the
// queries
static void totalCount(int[][] A, int N,
int M, int[][] queries, int Q)
{
// Stores the sum of each row
int row_sum[] = new int[N];
// Stores the sum of each col
int col_sum[] = new int[M];
// Traverse the matrix and calculate
// sum of each row and column
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
row_sum[i] += A[i][j];
col_sum[j] += A[i][j];
}
}
ArrayList<Integer> sum_list
= new ArrayList<>();
// Insert all row sums in sum_list
for (int i = 0; i < N; i++)
sum_list.add(row_sum[i]);
// Insert all column sums in sum_list
for (int i = 0; i < M; i++)
sum_list.add(col_sum[i]);
// Sort the array in ascending order
Collections.sort(sum_list);
// Traverse the array queries[][]
for (int i = 0; i < Q; i++) {
int L = queries[i][0];
int R = queries[i][1];
// Search the leftmost index of L
int l = left_search(sum_list, L);
// Search the rightmost index of R
int r = right_search(sum_list, R);
System.out.print(r - l + 1 + " ");
}
}
// Function to search for the
// leftmost index of given number
static int left_search(
ArrayList<Integer> A,
int num)
{
// Initialize low, high and ans
int low = 0, high = A.size() - 1;
int ans = 0;
while (low <= high) {
// Stores mid
int mid = low + (high - low) / 2;
// If A[mid] >= num
if (A.get(mid) >= num) {
ans = mid;
high = mid - 1;
}
else {
low = mid + 1;
}
}
return ans;
}
// Function to search for the
// rightmost index of given number
static int right_search(
ArrayList<Integer> A,
int num)
{
// Initialise low, high and ans
int low = 0, high = A.size() - 1;
int ans = high;
while (low <= high) {
// Stores mid
int mid = low + (high - low) / 2;
// If A[mid] <= num
if (A.get(mid) <= num) {
// Update ans
ans = mid;
// Update mid
low = mid + 1;
}
else {
// Update high
high = mid - 1;
}
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Given dimensions of matrix
int N = 3, M = 2;
// Given matrix
int A[][] = { { 13, 3 },
{ 9, 4 },
{ 6, 10 } };
// Given number of queries
int Q = 2;
// Given queries
int queries[][] = { { 10, 20 }, { 25, 35 } };
// Function call to count the
// number row-sums and column-sums
// present in the given ranges
totalCount(A, N, M, queries, Q);
}
}
Python3
# Python3 program for the above approach from collections import deque from bisect import bisect_left, bisect_right # Function to preprocess the matrix to execute the # queries def totalCount(A, N, M, queries, Q): # Stores the sum of each row row_sum = [0]*N # Stores the sum of each col col_sum = [0]*M # Traverse the matrix and calculate # sum of each row and column for i in range(N): for j in range(M): row_sum[i] += A[i][j] col_sum[j] += A[i][j] sum_list = [] # Insert all row sums in sum_list for i in range(N): sum_list.append(row_sum[i]) # Insert all column sums in sum_list for i in range(M): sum_list.append(col_sum[i]) # Sort the array in ascending order sum_list = sorted(sum_list) # Traverse the array queries[][] for i in range(Q): L = queries[i][0] R = queries[i][1] # Search the leftmost index of L l = left_search(sum_list, L) # Search the rightmost index of R r = right_search(sum_list, R) print(r - l + 1, end = " ") # Function to search for the # leftmost index of given number def left_search(A, num): # Initialize low, high and ans low, high = 0, len(A) - 1 ans = 0 while (low <= high): # Stores mid mid = low + (high - low) // 2 # If A[mid] >= num if (A[mid] >= num): ans = mid high = mid - 1 else: low = mid + 1 return ans # Function to search for the # rightmost index of given number def right_search(A, num): # Initialise low, high and ans low, high = 0, len(A) - 1 ans = high while (low <= high): # Stores mid mid = low + (high - low) // 2 # If A[mid] <= num if (A[mid] <= num): # Update ans ans = mid # Update mid low = mid + 1 else: # Update high high = mid - 1 return ans # Driver Code if __name__ == '__main__': # Given dimensions of matrix N, M = 3, 2 # Given matrix A = [ [ 13, 3 ], [ 9, 4 ], [ 6, 10 ] ] # Given number of queries Q = 2 # Given queries queries= [ [ 10, 20 ], [ 25, 35 ] ] # Function call to count the # number row-sums and column-sums # present in the given ranges totalCount(A, N, M, queries, Q) # This code is contributed by mohit kumar 29.
C#
using System;
using System.Collections.Generic;
class GFG
{
// Function to preprocess the matrix to execute the
// queries
static void totalCount(int[,] A, int N, int M,
int[,] queries, int Q)
{
// Stores the sum of each row
int []row_sum = new int[N];
// Stores the sum of each col
int []col_sum = new int[M];
// Traverse the matrix and calculate
// sum of each row and column
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
row_sum[i] += A[i,j];
col_sum[j] += A[i,j];
}
}
List<int> sum_list = new List<int>();
// Insert all row sums in sum_list
for (int i = 0; i < N; i++)
sum_list.Add(row_sum[i]);
// Insert all column sums in sum_list
for (int i = 0; i < M; i++)
sum_list.Add(col_sum[i]);
// Sort the array in ascending order
sum_list.Sort();
// Traverse the array queries[][]
for (int i = 0; i < Q; i++) {
int L = queries[i,0];
int R = queries[i,1];
// Search the leftmost index of L
int l = left_search(sum_list, L);
// Search the rightmost index of R
int r = right_search(sum_list, R);
Console.Write(r - l + 1 + " ");
}
}
// Function to search for the
// leftmost index of given number
static int left_search(List<int> A, int num)
{
// Initialize low, high and ans
int low = 0, high = A.Count- 1;
int ans = 0;
while (low <= high)
{
// Stores mid
int mid = low + (high - low) / 2;
// If A[mid] >= num
if (A[mid] >= num) {
ans = mid;
high = mid - 1;
}
else {
low = mid + 1;
}
}
return ans;
}
// Function to search for the
// rightmost index of given number
static int right_search( List<int> A,int num)
{
// Initialise low, high and ans
int low = 0, high = A.Count- 1;
int ans = high;
while (low <= high) {
// Stores mid
int mid = low + (high - low) / 2;
// If A[mid] <= num
if (A[mid] <= num) {
// Update ans
ans = mid;
// Update mid
low = mid + 1;
}
else {
// Update high
high = mid - 1;
}
}
return ans;
}
//driver code
static void Main()
{
int N = 3, M = 2;
// Given matrix
int [,]A = new int[,]{ { 13, 3 },{ 9, 4 },{ 6, 10 } };
// Given number of queries
int Q = 2;
// Given queries
int [,]queries = new int[,]{ { 10, 20 }, { 25, 35 } };
// Function call to count the
// number row-sums and column-sums
// present in the given ranges
totalCount(A, N, M, queries, Q);
}
}
//This code is contributed by SoumikMondal
Javascript
<script>
// Javascript program for the above approach
// Function to preprocess the matrix to execute the
// queries
function totalCount(A,N,M,queries,Q)
{
// Stores the sum of each row
let row_sum = new Array(N);
// Stores the sum of each col
let col_sum = new Array(M);
for(let i=0;i<N;i++)
row_sum[i]=0;
for(let j=0;j<M;j++)
col_sum[j]=0;
// Traverse the matrix and calculate
// sum of each row and column
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
row_sum[i] += A[i][j];
col_sum[j] += A[i][j];
}
}
let sum_list=[];
// Insert all row sums in sum_list
for (let i = 0; i < N; i++)
sum_list.push(row_sum[i]);
// Insert all column sums in sum_list
for (let i = 0; i < M; i++)
sum_list.push(col_sum[i]);
// Sort the array in ascending order
(sum_list).sort(function(a,b){return a-b;});
// Traverse the array queries[][]
for (let i = 0; i < Q; i++) {
let L = queries[i][0];
let R = queries[i][1];
// Search the leftmost index of L
let l = left_search(sum_list, L);
// Search the rightmost index of R
let r = right_search(sum_list, R);
document.write(r - l + 1 + " ");
}
}
// Function to search for the
// leftmost index of given number
function left_search(A,num)
{
// Initialize low, high and ans
let low = 0, high = A.length - 1;
let ans = 0;
while (low <= high) {
// Stores mid
let mid = low + Math.floor((high - low) / 2);
// If A[mid] >= num
if (A[mid] >= num) {
ans = mid;
high = mid - 1;
}
else {
low = mid + 1;
}
}
return ans;
}
// Function to search for the
// rightmost index of given number
function right_search(A,num)
{
// Initialise low, high and ans
let low = 0, high = A.length - 1;
let ans = high;
while (low <= high) {
// Stores mid
let mid = low + Math.floor((high - low) / 2);
// If A[mid] <= num
if (A[mid] <= num) {
// Update ans
ans = mid;
// Update mid
low = mid + 1;
}
else {
// Update high
high = mid - 1;
}
}
return ans;
}
// Given dimensions of matrix
let N = 3, M = 2;
// Given matrix
let A=[[ 13, 3 ],[ 9, 4 ],[ 6, 10 ] ];
// Given number of queries
let Q = 2;
let queries=[[ 10, 20 ], [ 25, 35 ]];
// Function call to count the
// number row-sums and column-sums
// present in the given ranges
totalCount(A, N, M, queries, Q);
// This code is contributed by unknown2108
</script>
Producción:
4 1
Complejidad de Tiempo: O(Q * log(N * M))
Espacio Auxiliar: O(N * M)
Publicación traducida automáticamente
Artículo escrito por hemanthswarna1506 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA