Dada una array , arr[] de tamaño N y un entero T. La tarea es encontrar para cada índice el número mínimo de índices que deben omitirse si la suma hasta el i-ésimo índice no debe exceder T.
Ejemplos:
Entrada: N = 7, T = 15, arr[] = {1, 2, 3, 4, 5, 6, 7}
Salida: 0 0 0 0 0 2 3
Explicación: No es necesario omitir ningún índice para los primeros 5 índices: {1, 2, 3, 4, 5}, ya que su suma es 15 y <= T.
Para el sexto índice, se pueden omitir los índices 3 y 4, lo que hace que su suma = (1+2+3+6 ) = 12.
Para el séptimo, se pueden omitir los índices 3, 4 y 5, lo que hace que su suma = (1+2+3+7) = 13.Entrada: N =2, T = 100, arr[] = {100, 100}
Salida: 0 1
Enfoque: La idea es usar un mapa para almacenar los elementos visitados en orden creciente mientras se recorre. Siga los pasos a continuación para resolver el problema:
- Cree un mapa ordenado , M para llevar un recuento de los elementos antes del i-ésimo índice.
- Inicialice una suma variable como 0 para almacenar la suma del prefijo.
- Atraviesa la array , arr[] usando la variable i
- Almacene la diferencia de sum+arr[i] y T en una variable, d .
- Si el valor de d>0 , recorre el mapa desde el final y selecciona los índices con los elementos más grandes hasta que la suma sea menor que T. Almacene el número de elementos requeridos en una variable k .
- Agregue arr[i] a la suma e incremente A[i] en M en 1 .
- Imprime el valor de k .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ approach for above approach #include <bits/stdc++.h> using namespace std; // Function to calculate minimum indices to be skipped // so that sum till i remains smaller than T void skipIndices(int N, int T, int arr[]) { // Store the sum of all indices before i int sum = 0; // Store the elements that can be skipped map<int, int> count; // Traverse the array, A[] for (int i = 0; i < N; i++) { // Store the total sum of elements that // needs to be skipped int d = sum + arr[i] - T; // Store the number of elements need // to be removed int k = 0; if (d > 0) { // Traverse from the back of map so // as to take bigger elements first for (auto u = count.rbegin(); u != count.rend(); u++) { int j = u->first; int x = j * count[j]; if (d <= x) { k += (d + j - 1) / j; break; } k += count[j]; d -= x; } } // Update sum sum += arr[i]; // Update map with the current element count[arr[i]]++; cout << k << " "; } } // Driver code int main() { // Given Input int N = 7; int T = 15; int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; // Function Call skipIndices(N, T, arr); return 0; }
Java
import java.util.ArrayList; import java.util.Map; import java.util.TreeMap; // C++ approach for above approach class GFG { // Function to calculate minimum indices to be skipped // so that sum till i remains smaller than T public static void skipIndices(int N, int T, int arr[]) { // Store the sum of all indices before i int sum = 0; // Store the elements that can be skipped TreeMap<Integer, Integer> count = new TreeMap<Integer, Integer>(); // Traverse the array, A[] for (int i = 0; i < N; i++) { // Store the total sum of elements that // needs to be skipped int d = sum + arr[i] - T; // Store the number of elements need // to be removed int k = 0; if (d > 0) { // Traverse from the back of map so // as to take bigger elements first for (Map.Entry<Integer, Integer> u : count.descendingMap().entrySet()) { int j = u.getKey(); int x = j * count.get(j); if (d <= x) { k += (d + j - 1) / j; break; } k += count.get(j); d -= x; } } // Update sum sum += arr[i]; // Update map with the current element if(count.containsKey(arr[i])){ count.put(arr[i], count.get(arr[i]) + 1); }else{ count.put(arr[i], 1); } System.out.print(k + " "); } } // Driver code public static void main(String args[]) { // Given Input int N = 7; int T = 15; int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; // Function Call skipIndices(N, T, arr); } } // This code is contributed by _saurabh_jaiswal.
Python3
# Python3 approach for above approach # Function to calculate minimum indices to be skipped # so that sum till i remains smaller than T def skipIndices(N, T, arr): # Store the sum of all indices before i sum = 0 # Store the elements that can be skipped count = {} # Traverse the array, A[] for i in range(N): # Store the total sum of elements that # needs to be skipped d = sum + arr[i] - T # Store the number of elements need # to be removed k = 0 if (d > 0): # Traverse from the back of map so # as to take bigger elements first for u in list(count.keys())[::-1]: j = u x = j * count[j] if (d <= x): k += (d + j - 1) // j break k += count[j] d -= x # Update sum sum += arr[i] # Update map with the current element count[arr[i]] = count.get(arr[i], 0) + 1 print(k, end = " ") # Driver code if __name__ == '__main__': # Given Input N = 7 T = 15 arr = [1, 2, 3, 4, 5, 6, 7] # Function Call skipIndices(N, T, arr) # This code is contributed by mohit kumar 29.
Javascript
<script> // Javascript approach for above approach // Function to calculate minimum indices // to be skipped so that sum till i // remains smaller than T function skipIndices(N, T, arr) { // Store the sum of all indices before i let sum = 0; // Store the elements that can be skipped let count = new Map(); // Traverse the array, A[] for(let i = 0; i < N; i++) { // Store the total sum of elements that // needs to be skipped let d = sum + arr[i] - T; // Store the number of elements need // to be removed let k = 0; if (d > 0) { // Traverse from the back of map so // as to take bigger elements first for(let u of [...count.keys()].reverse()) { let j = u; let x = j * count.get(j); if (d <= x) { k += Math.floor((d + j - 1) / j); break; } k += count.get(j); d -= x; } } // Update sum sum += arr[i]; // Update map with the current element if (count.has(arr[i])) { count.set(arr[i], count.get(i) + 1) } else { count.set(arr[i], 1) } document.write(k + " "); } } // Driver code // Given Input let N = 7; let T = 15; let arr = [ 1, 2, 3, 4, 5, 6, 7 ]; // Function Call skipIndices(N, T, arr); // This code is contributed by _saurabh_jaiswal </script>
0 0 0 0 0 2 3
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar : O(N)