Dado un entero positivo N y una array ordenada arr[] que consta de M enteros, la tarea es encontrar el valor absoluto mínimo de (K – arr[i]) para todos los valores posibles de K en el rango [0, N – 1 ] .
Ejemplos:
Entrada: N = 5, arr[] = {0, 4}
Salida: 0 1 2 1 0
Explicación:
A continuación se muestra el valor mínimo posible para todos los valores posibles de K en el rango [0, N – 1]:
- K = 0: El valor mínimo de abs(K – arr[i]) se obtiene considerando arr[i] como 0. Por lo tanto, el valor es abs(0 – 0) = 0.
- K = 1: El valor mínimo de abs(K – arr[i]) se obtiene considerando arr[i] como 0. Por lo tanto, el valor es abs(1 – 0) = 1.
- K = 2: El valor mínimo de abs(K – arr[i]) se obtiene considerando arr[i] como 0. Por lo tanto, el valor es abs(2 – 0) = 2.
- K = 3: El valor mínimo de abs(K – arr[i]) se obtiene considerando arr[i] como 4. Por lo tanto, el valor es abs(3 – 4) = 1.
- K = 4: El valor mínimo de abs(K – arr[i]) se obtiene considerando arr[i] como 4. Por lo tanto, el valor es abs(4 – 4) = 0.
Entrada: N = 6, arr[] = {0, 1, 4, 5}
Salida: 0 0 1 1 0 0
Enfoque: el problema dado se puede resolver eligiendo el valor de la array que es mayor o menor que el valor actual de K . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos ind como 0 , y una variable, digamos prev to arr[0] que almacene el valor previamente asignado.
- Iterar sobre el rango [0, N – 1] usando la variable K y realizar los siguientes pasos:
- Inicialice una variable, digamos distancia para almacenar el valor absoluto mínimo de (K – arr[i]) .
- Si el valor de i es menor que arr[0] , actualice el valor de la distancia a (arr[0] – i) .
- De lo contrario, si el valor de i es al menos prev , el valor de (ind + 1) es menor que M y el valor de i es como máximo arr[ind + 1] , luego realice los siguientes pasos:
- Actualice el valor de la distancia al mínimo de (i – prev) y (arr[ind + 1] – i) .
- Si el valor de i es igual a arr[ind + 1] , actualice el valor de distance a 0 , prev a arr[ind + 1] e incremente el valor de ind en 1 .
- Si el valor de i es mayor que prev , actualice el valor de distancia a (i – prev) .
- Después de completar los pasos anteriores, imprima el valor de la distancia como el valor absoluto mínimo de (K – arr[i]) para el valor actual de 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; // Function to find the minimum absolute // value of (K - arr[i]) for each possible // value of K over the range [0, N - 1]| void minimumDistance(vector<int> arr, int N) { int ind = 0; int prev = arr[ind]; int s = arr.size(); // Traverse the given array arr[] for (int i = 0; i < N; i++) { // Stores the mininimum distance // to any array element arr[i] int distance = INT_MAX; // Check if there is no safe // position smaller than i if (i < arr[0]) { distance = arr[0] - i; } // Check if the current position // is between two safe positions else if (i >= prev && ind + 1 < s && i <= arr[ind + 1]) { // Take the minimum of two // distances distance = min(i - prev, arr[ind + 1] - i); // Check if the current index // is a safe position if (i == arr[ind + 1]) { distance = 0; prev = arr[ind + 1]; ind++; } } // Check if there is no safe // position greater than i else { distance = i - prev; } // Print the minimum distance cout << distance << " "; } } // Driver Code int main() { int N = 5; vector<int> arr = { 0, 4 }; minimumDistance(arr, N); return 0; }
Java
// Java program for the above approach import java.io.*; class GFG { // Functinion to find the minimum absolute // value of (K - arr[i]) for each possible // value of K over the range [0, N - 1]| public static void minimumDistance(int arr[], int N) { int ind = 0; int prev = arr[ind]; int s = arr.length; // Traverse the given array arr[] for (int i = 0; i < N; i++) { // Stores the mininimum distance // to any array element arr[i] int distance = Integer.MAX_VALUE; // Check if there is no safe // position smaller than i if (i < arr[0]) { distance = arr[0] - i; } // Check if the current position // is between two safe positions else if (i >= prev && ind + 1 < s && i <= arr[ind + 1]) { // Take the minimum of two // distances distance = Math.min(i - prev, arr[ind + 1] - i); // Check if the current index // is a safe position if (i == arr[ind + 1]) { distance = 0; prev = arr[ind + 1]; ind++; } } // Check if there is no safe // position greater than i else { distance = i - prev; } // Print the minimum distance System.out.print(distance+" "); } } // driver code public static void main (String[] args) { int N = 5; int arr[] = { 0, 4 }; minimumDistance(arr, N); } } // This code is contributed by Manu Pathria
Python3
# Python program for the above approach # Function to find the minimum absolute # value of (K - arr[i]) for each possible # value of K over the range [0, N - 1]| def minimumDistance(arr, N): ind = 0; prev = arr[ind]; s = len(arr); # Traverse the given array arr[] for i in range(N): # Stores the mininimum distance # to any array element arr[i] distance = 10**9; # Check if there is no safe # position smaller than i if (i < arr[0]): distance = arr[0] - i; # Check if the current position # is between two safe positions elif (i >= prev and ind + 1 < s and i <= arr[ind + 1]): # Take the minimum of two # distances distance = min(i - prev, arr[ind + 1] - i); # Check if the current index # is a safe position if (i == arr[ind + 1]): distance = 0; prev = arr[ind + 1]; ind += 1; # Check if there is no safe # position greater than i else: distance = i - prev; # Print the minimum distance print(distance, end=" "); # Driver Code N = 5; arr = [0, 4]; minimumDistance(arr, N); # This code is contributed by _saurabh_jaiswal.
C#
// C# program for the above approach using System; class GFG { // Functinion to find the minimum absolute // value of (K - arr[i]) for each possible // value of K over the range [0, N - 1]| public static void minimumDistance(int []arr, int N) { int ind = 0; int prev = arr[ind]; int s = arr.Length; // Traverse the given array arr[] for (int i = 0; i < N; i++) { // Stores the mininimum distance // to any array element arr[i] int distance = Int32.MaxValue; // Check if there is no safe // position smaller than i if (i < arr[0]) { distance = arr[0] - i; } // Check if the current position // is between two safe positions else if (i >= prev && ind + 1 < s && i <= arr[ind + 1]) { // Take the minimum of two // distances distance = Math.Min(i - prev, arr[ind + 1] - i); // Check if the current index // is a safe position if (i == arr[ind + 1]) { distance = 0; prev = arr[ind + 1]; ind++; } } // Check if there is no safe // position greater than i else { distance = i - prev; } // Print the minimum distance Console.Write(distance+" "); } } // driver code public static void Main (string[] args) { int N = 5; int []arr = { 0, 4 }; minimumDistance(arr, N); } } // This code is contributed by ukasp.
Javascript
<script> // JavaScript program for the above approach // Function to find the minimum absolute // value of (K - arr[i]) for each possible // value of K over the range [0, N - 1]| function minimumDistance(arr, N) { let ind = 0; let prev = arr[ind]; let s = arr.length; // Traverse the given array arr[] for (let i = 0; i < N; i++) { // Stores the mininimum distance // to any array element arr[i] let distance = Number.MAX_SAFE_INTEGER; // Check if there is no safe // position smaller than i if (i < arr[0]) { distance = arr[0] - i; } // Check if the current position // is between two safe positions else if (i >= prev && ind + 1 < s && i <= arr[ind + 1]) { // Take the minimum of two // distances distance = Math.min(i - prev, arr[ind + 1] - i); // Check if the current index // is a safe position if (i == arr[ind + 1]) { distance = 0; prev = arr[ind + 1]; ind++; } } // Check if there is no safe // position greater than i else { distance = i - prev; } // Print the minimum distance document.write(distance + " "); } } // Driver Code let N = 5; let arr = [0, 4]; minimumDistance(arr, N); </script>
0 1 2 1 0
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por manupathria y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA