Valor absoluto mínimo de (K – arr[i]) para todos los valores posibles de K en el rango [0, N – 1]

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++ 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 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

# 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# 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.

<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)