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