Dada una array arr[] de tamaño N , un número entero K y Q consultas, cada una de las formas {x, l, r} . Para cada consulta, la tarea es encontrar el recuento de todos los elementos en el rango de índice [l, r] que tienen un resto x cuando se divide por K .
Ejemplos:
Entrada: arr[] = {15, 28, 72, 43, 20, 0, 97}, K = 5, consultas[] = {{3, 0, 3}, {0, 0, 6}, {6, 2, 4}}
Salida: 2, 3, 0
Explicación: Para la primera consulta, hay 2 elementos en el rango [0, 3] cuyo resto es 3 (28, 43).
De manera similar, 3 elementos en el rango [0, 6] cuyo resto es 0 (15, 20, 0).
En la tercera consulta se deben encontrar los elementos cuyo resto sea 6.
Pero para el K = 5 dado, los restos posibles son solo [0, 4]. Entonces, para cualquier x >= K, la respuesta será 0.Entrada: arr[] = {2, 4, 6, 7, 5}, K = 3, consultas[] = {{2, 1, 4}}
Salida: 1
Método 1: un enfoque simple es, para cada consulta, iterar de l a r y contar todos los elementos cuyo resto sea x .
Complejidad temporal: O(N * Q)
Espacio auxiliar: O(1)
Método 2: este problema también se puede resolver con la ayuda de un cálculo previo basado en la siguiente idea:
Calcule previamente cuál será el resto, cuando arr[i] se divide por K y guárdelo en una array (digamos mat[] ) donde mat[i][j] representa el resto de arr[j] es i cuando se divide por K .
Ahora, la suma del prefijo de la i-ésima fila de la array da el recuento de elementos que tendrán un resto i cuando se dividan por K. Por lo tanto, después del prefijo sum mat[i][j] representará el recuento total de elementos hasta el índice jth que tiene el resto i cuando se divide por K.
Entonces, para una consulta {x, l, r}, la respuesta será(mat[x][r] – mat[x][l] [+1 si arr[l]%K es x])
Siga la ilustración a continuación para una mejor comprensión de la construcción de la array.
Ilustración:
Considere arr[] = {15, 28, 72, 43, 20, 0, 97}, K = 5
Cree una array 2D llamada precompute , de tamaño (K*N) e inicialícela con 0.
Para el i -ésimo elemento, marque precompute[arr[i]%K][i] = 1 , haga esto para todos los estados i que el i-ésimo elemento tiene resto arr[i]%K.Para el ejemplo dado, nuestra array de cálculo previo tendrá el siguiente aspecto donde fila: resto , columna: número de índice .
0 1 2 3 4 5 6 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 0 2 0 0 1 0 0 0 1 3 0 1 0 1 0 0 0 4 0 0 0 0 0 0 0 Luego, para cada fila, calcule la suma del prefijo. Ahora la array se verá así:
0 1 2 3 4 5 6 0 1 1 1 1 2 3 3 1 0 0 0 0 0 0 0 2 0 0 1 1 1 1 2 3 0 1 1 2 2 2 2 4 0 0 0 0 0 0 0 Aquí precalcular[0][6] indica que hasta el sexto índice hay un total de 3 elementos que tendrán un resto 3 cuando se divida por 5.
Siga los pasos mencionados a continuación para implementar la idea:
- Cree la array 2D (digamos precálculo ).
- Construya la array como se mencionó anteriormente.
- Recorrer las consultas:
- Para cada consulta, calcule la cantidad de elementos según la fórmula que se muestra arriba y guárdela en la array de respuesta.
- Devuelve la array que tiene las respuestas.
Nota: este método es más eficiente solo cuando el número de consultas es mayor que K .
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;
const int MXN = 2e5;
int precompute[100][MXN];
// To precompute count prefix sum of all
// possible remainders
void precomputation(int arr[], int n, int k)
{
// Mark cell whose remainder is arr[i]%k
for (int i = 0; i < n; i++)
precompute[arr[i] % k][i] = 1;
// Take prefix sum for all rows
for (int i = 0; i < k; i++) {
for (int j = 1; j < n; j++) {
precompute[i][j]
+= precompute[i][j - 1];
}
}
}
// Function to find the
// count of numbers for the queries
vector<int> findCount(int arr[], int K, int N,
vector<vector<int> >& queries)
{
vector<int> res;
// Initialise matrix with 0
memset(precompute, 0, sizeof precompute);
// To calculate count of remainders
precomputation(arr, N, K);
for (int i = 0; i < queries.size(); i++) {
int x = queries[i][0];
int l = queries[i][1];
int r = queries[i][2];
if (x >= K) {
res.push_back(0);
continue;
}
int count = precompute[x][r]
- precompute[x][l]
+ (arr[l] % K == x);
res.push_back(count);
}
return res;
}
// Driver code
int main()
{
int arr[] = { 15, 28, 72, 43, 20, 0, 97 };
int K = 5;
int N = sizeof(arr) / sizeof(arr[0]);
vector<vector<int> > queries{ { 3, 0, 3 },
{ 0, 0, 6 },
{ 6, 2, 4 } };
vector<int> ans
= findCount(arr, K, N, queries);
for (int x : ans)
cout << x << " ";
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.ArrayList;
class GFG {
static int MXN = 200000;
static int[][] precompute = new int[100][MXN];
// To precompute count prefix sum of all
// possible remainders
static void precomputation(int[] arr, int n, int k)
{
// Mark cell whose remainder is arr[i]%k
for (int i = 0; i < n; i++)
precompute[arr[i] % k][i] = 1;
// Take prefix sum for all rows
for (int i = 0; i < k; i++) {
for (int j = 1; j < n; j++) {
precompute[i][j] += precompute[i][j - 1];
}
}
}
// Function to find the
// count of numbers for the queries
static ArrayList<Integer>
findCount(int[] arr, int K, int N, int[][] queries)
{
ArrayList<Integer> res = new ArrayList<Integer>();
// Initialise matrix with 0
for (int i = 0; i < 100; i++) {
for (int j = 0; j < MXN; j++)
precompute[i][j] = 0;
}
// To calculate count of remainders
precomputation(arr, N, K);
for (int i = 0; i < queries.length; i++) {
int x = queries[i][0];
int l = queries[i][1];
int r = queries[i][2];
if (x >= K) {
res.add(0);
continue;
}
int count = precompute[x][r] - precompute[x][l]
+ ((arr[l] % K == x) ? 1 : 0);
res.add(count);
}
return res;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 15, 28, 72, 43, 20, 0, 97 };
int K = 5;
int N = arr.length;
int[][] queries
= { { 3, 0, 3 }, { 0, 0, 6 }, { 6, 2, 4 } };
ArrayList<Integer> ans
= findCount(arr, K, N, queries);
for (int i = 0; i < ans.size(); i++)
System.out.print(ans.get(i) + " ");
}
}
// This code is contributed by phasing17
Python3
# python3 program for the above approach MXN = int(2e5) precompute = [[0 for _ in range(MXN)] for _ in range(100)] # To precompute count prefix sum of all # possible remainders def precomputation(arr, n, k): global precompute # Mark cell whose remainder is arr[i]%k for i in range(0, n): precompute[arr[i] % k][i] = 1 # Take prefix sum for all rows for i in range(0, k): for j in range(1, n): precompute[i][j] += precompute[i][j - 1] # Function to find the # count of numbers for the queries def findCount(arr, K, N, queries): global precompute res = [] # Initialise matrix with 0 # To calculate count of remainders precomputation(arr, N, K) for i in range(0, len(queries)): x = queries[i][0] l = queries[i][1] r = queries[i][2] if (x >= K): res.append(0) continue count = precompute[x][r] - precompute[x][l] + (arr[l] % K == x) res.append(count) return res # Driver code if __name__ == "__main__": arr = [15, 28, 72, 43, 20, 0, 97] K = 5 N = len(arr) queries = [[3, 0, 3], [0, 0, 6], [6, 2, 4]] ans = findCount(arr, K, N, queries) for x in ans: print(x, end=" ") # This code is contributed by rakeshsahni
C#
// C# code for the above discussed approach
using System;
using System.Collections;
public class GFG {
static int MXN = 200000;
static int[, ] precompute = new int[100, MXN];
// To precompute count prefix sum of all
// possible remainders
static void precomputation(int[] arr, int n, int k)
{
// Mark cell whose remainder is arr[i]%k
for (int i = 0; i < n; i++)
precompute[arr[i] % k, i] = 1;
// Take prefix sum for all rows
for (int i = 0; i < k; i++) {
for (int j = 1; j < n; j++) {
precompute[i, j] += precompute[i, j - 1];
}
}
}
// Function to find the
// count of numbers for the queries
static ArrayList findCount(int[] arr, int K, int N,
int[, ] queries)
{
var res = new ArrayList();
// Initialise matrix with 0
for (int i = 0; i < 100; i++) {
for (int j = 0; j < MXN; j++)
precompute[i, j] = 0;
}
// To calculate count of remainders
precomputation(arr, N, K);
for (int i = 0; i < queries.GetLength(0); i++) {
int x = queries[i, 0];
int l = queries[i, 1];
int r = queries[i, 2];
if (x >= K) {
res.Add(0);
continue;
}
int count = precompute[x, r] - precompute[x, l]
+ ((arr[l] % K == x) ? 1 : 0);
res.Add(count);
}
return res;
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 15, 28, 72, 43, 20, 0, 97 };
int K = 5;
int N = arr.Length;
int[, ] queries
= { { 3, 0, 3 }, { 0, 0, 6 }, { 6, 2, 4 } };
ArrayList ans = findCount(arr, K, N, queries);
for (int i = 0; i < ans.Count; i++)
Console.Write(ans[i] + " ");
}
}
// This code is contributed by phasing17
Javascript
<script>
// JavaScript code for the above approach
let MXN = 2e5;
let precompute = new Array(100);
for (let i = 0; i < precompute.length; i++) {
precompute[i] = new Array(MXN).fill(0);
}
// To precompute count prefix sum of all
// possible remainders
function precomputation(arr, n, k)
{
// Mark cell whose remainder is arr[i]%k
for (let i = 0; i < n; i++)
precompute[arr[i] % k][i] = 1;
// Take prefix sum for all rows
for (let i = 0; i < k; i++) {
for (let j = 1; j < n; j++) {
precompute[i][j]
+= precompute[i][j - 1];
}
}
}
// Function to find the
// count of numbers for the queries
function findCount(arr, K, N, queries) {
let res = [];
// To calculate count of remainders
precomputation(arr, N, K);
for (let i = 0; i < queries.length; i++) {
let x = queries[i][0];
let l = queries[i][1];
let r = queries[i][2];
if (x >= K) {
res.push(0);
continue;
}
let count = precompute[x][r]
- precompute[x][l]
+ (arr[l] % K == x);
res.push(count);
}
return res;
}
// Driver code
let arr = [15, 28, 72, 43, 20, 0, 97];
let K = 5;
let N = arr.length;
let queries = [[3, 0, 3],
[0, 0, 6],
[6, 2, 4]];
let ans
= findCount(arr, K, N, queries);
for (let x of ans)
document.write(x + " ")
// This code is contributed by Potta Lokesh
</script>
2 3 0
Complejidad temporal: O(Q + K*N)
Espacio auxiliar: O(K*N)
Publicación traducida automáticamente
Artículo escrito por patilnainesh911 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA