Dada una array arr[] de tamaño N que contiene números distintos del 1 al N en cualquier orden, la tarea es realizar una suma de rango modificada en esta array de acuerdo con las siguientes reglas.
Para cada índice ‘ i ‘ en la array arr :
- El índice inicial del rango ‘ L ‘ se selecciona como i + 1
- El índice final del rango ‘ R ‘ se selecciona como:
- min(arr[i], N-1) ; si arr[i] > i
- max(i+1, array[i]) ; si arr[i] < i+1
- Para la actualización, los valores en el rango arr[L] a arr[R] se incrementan en 1.
- El rango se encuentra usando la array de entrada y no la array actualizada
Ejemplos:
Entrada: arr[] = {4, 1, 3, 2}
Salida: 4 2 5 4
Explicación:
Para i = 0 -> Elemento en la array de entrada = 4. Por lo tanto, L = 1 y R = min(4, N- 1) = 3. Por lo tanto, todos los elementos de arr[1] a arr[3] se incrementan en 1. Los elementos después de la operación de actualización son {4, 2, 4, 3}.
Para i = 1 -> Elemento en la array de entrada = 1. Por lo tanto, L = 2 y R = max(1, i+1) = 2. Por lo tanto, todos los elementos desde arr[2] hasta arr[2] se incrementan en 1. Los elementos después de la operación de actualización son {4, 2, 5, 3}.
Para i = 2 -> Elemento en la array de entrada = 3. Por lo tanto, L = 3 y R = min(3, N-1) = 3. Por lo tanto, todos los elementos desde arr[3] hasta arr[3] se incrementan en 1. Los elementos después de la operación de actualización son {4, 2, 5, 4}.
Para i = 3 -> La array no se ve afectada. Por lo tanto, los elementos después de la operación de actualización son {4, 2, 5, 4}.
La array resultante es {4, 2, 5, 4}.
Entrada: arr[] = {2, 1}
Salida: {2, 2}
Explicación:
El primer elemento es 2. Entonces arr[1] se incrementa en 1. Por lo tanto, la array resultante es {2, 2}.
Enfoque ingenuo: El enfoque ingenuo consiste en ejecutar un bucle para cada elemento y aumentar todos los valores de arr[i+1] a arr[min(i+arr[i], N-1)] en 1. La complejidad temporal de este enfoque es O(N 2 ) .
Enfoque eficiente: este problema se puede resolver en O(N) usando un espacio extra de O(N). La idea es utilizar el concepto de array de suma de prefijos . Se siguen los siguientes pasos para calcular la respuesta:
- Se declara un arreglo b[] de tamaño N + 1 y todos los elementos se inicializan con 0.
- Para cada elemento arr[i] en la array dada, se suma 1 a b[i+1] y se resta de b[min(i + arr[i], N – 1)+ 1] .
- Luego, se calcula la suma del prefijo de la array b[] .
- Finalmente, arr se actualiza como arr[i] = arr[i] + b[i] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find elements in an array // after performing range updates. #include <bits/stdc++.h> using namespace std; // Function to perform the update on the given // input array arr[]. void update(vector<int>& arr, vector<int>& d, int n) { // A new array of size N+1 is defined // and 1's are added in that array for (int i = 0; i < n - 1; i++) { d[i + 1] += 1; d[min(i + arr[i], n - 1) + 1] -= 1; } // Loop to perform the prefix sum // on the array d[]. for (int i = 1; i < n; i++) { d[i] = d[i] + d[i - 1]; } } // Function to print the final // array after updation void print(vector<int>& arr, vector<int>& d, int n) { // Loop to add the values of d[i] // to arr[i] for (int i = 0; i < n; i++) cout << arr[i] + d[i] << " "; } // Function to perform modified range sum void modifiedRangeSum(vector<int>& arr, int n) { vector<int> d; // Loop to add N+1 0's in array d[] for (int i = 0; i <= n; i++) d.push_back(0); update(arr, d, n); print(arr, d, n); } // Driver code int main() { vector<int> arr = { 5, 4, 1, 3, 2 }; int n = 5; modifiedRangeSum(arr, n); return 0; }
Java
// Java program to find elements in an array // after performing range updates. import java.util.*; class GFG{ static ArrayList<Integer> arr = new ArrayList<Integer>(Arrays.asList(5, 4, 1, 3, 2)); static int n = 5; // Function to perform the update on the given // input array arr[]. static void update(ArrayList<Integer> d) { // A new array of size N+1 is defined // and 1's are added in that array for (int i = 0; i < n - 1; i++) { d.set(i + 1,d.get(i+1)+1); int x = Math.min(i + arr.get(i), n - 1)+ 1; d.set(x,d.get(x)-1); } // Loop to perform the prefix sum // on the array d[]. for (int i = 1; i < n; i++) { d.set(i,d.get(i)+d.get(i - 1)); } } // Function to print the final // array after updation static void print(ArrayList<Integer> d) { // Loop to add the values of d[i] // to arr[i] for (int i = 0; i < n; i++) System.out.print(arr.get(i) + d.get(i)+ " "); } // Function to perform modified range sum static void modifiedRangeSum() { ArrayList<Integer> d = new ArrayList<Integer>(); // Loop to add N+1 0's in array d[] for (int i = 0; i <= n; i++) d.add(0); update(d); print(d); } // Driver code public static void main(String args[]) { modifiedRangeSum(); } } // This code is contributed by Surendra_Gangwar
Python3
# Python3 program to find elements in an array # after performing range updates. arr = [] d = [] # Function to perform the update on the given # input array arr[]. def update( n): global d global arr # A new array of size N+1 is defined # and 1's are added in that array for i in range(n - 1): d[i + 1] += 1 d[min(i + arr[i], n - 1) + 1] -= 1 # Loop to perform the prefix sum # on the array d[]. for i in range(n): d[i + 1] = d[i + 1] + d[i ] # Function to print the final # array after updation def print_( n): global d global arr # Loop to add the values of d[i] # to arr[i] for i in range(n): x = (arr[i] + d[i] ) print(x, end = " ") # Function to perform modified range sum def modifiedRangeSum( n): global d global arr d = [] # Loop to add N+1 0's in array d[] for i in range(n + 1): d.append(0) update( n) print_(n) # Driver code arr = [5, 4, 1, 3, 2] n = 5 modifiedRangeSum( n) # This code is contributed by Arnab Kundu
C#
// C# program to find elements in an array // after performing range updates. using System; class GFG { // Function to perform the update on the given // input array arr[]. static void update(int []arr,int [] d, int n){ // A new array of size N+1 is defined // and 1's are added in that array for (int i = 0; i < n - 1; i++) { d[i + 1] += 1; d[Math.Min(i + arr[i], n - 1) + 1] -= 1; } // Loop to perform the prefix sum // on the array d[]. for (int i = 1; i < n; i++) { d[i] = d[i] + d[i - 1]; } } // Function to print the final // array after updation static void print(int []arr,int []d, int n) { // Loop to add the values of d[i] // to arr[i] for (int i = 0; i < n; i++) Console.Write((arr[i] + d[i])+" "); } // Function to perform modified range sum static void modifiedRangeSum(int []arr, int n) { int []d= new int[n+1]; // Loop to add N+1 0's in array d[] for (int i = 0; i <= n; i++) d[i]=0; update(arr, d, n); print(arr, d, n); } // Driver code public static void Main() { int [] arr = { 5, 4, 1, 3, 2 }; int n = 5; modifiedRangeSum(arr, n); } } // This code is contributed by mohit kumar 29
Javascript
<script> // Javascript program to find elements in an array // after performing range updates. // Function to perform the update on the given // input array arr[]. function update(arr, d, n) { // A new array of size N+1 is defined // and 1's are added in that array for (var i = 0; i < n - 1; i++) { d[i + 1] += 1; d[Math.min(i + arr[i], n - 1) + 1] -= 1; } // Loop to perform the prefix sum // on the array d[]. for (var i = 1; i < n; i++) { d[i] = d[i] + d[i - 1]; } } // Function to print the final // array after updation function print(arr, d, n) { // Loop to add the values of d[i] // to arr[i] for (var i = 0; i < n; i++) document.write( arr[i] + d[i] + " "); } // Function to perform modified range sum function modifiedRangeSum(arr, n) { var d = []; // Loop to add N+1 0's in array d[] for (var i = 0; i <= n; i++) d.push(0); update(arr, d, n); print(arr, d, n); } // Driver code var arr = [5, 4, 1, 3, 2]; var n = 5; modifiedRangeSum(arr, n); // This code is contributed by importantly. </script>
5 5 3 6 5
Publicación traducida automáticamente
Artículo escrito por promaroy20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA