Minimizar la diferencia entre los valores máximo y mínimo de la array modificada

Dada una array A de n enteros y un entero X. Puede elegir cualquier número entero entre  , y agregar k a A[i] para cada  . La tarea es encontrar la diferencia más pequeña posible entre el valor máximo de A y el valor mínimo de A después de actualizar la array A.
Ejemplos: 
 

Input: arr[] = {1, 3, 6}, x = 3
Output: 0
New array is [3, 3, 3] or [4, 4, 4].

Input: arr[] = {0, 10}, x = 2
Output: 6
New array is [2, 8] i.e add 2 to a[0] and subtract -2 from a[1].

Método: Sea A el arreglo original. Para tratar de minimizar max(A) – min(A) , intentemos minimizar max(A) y maximizar min(A) por separado.
El valor más pequeño posible de max(A) es max(A) – K , ya que el valor max(A) no puede bajar. De manera similar, el mayor valor posible de min(A) es min(A) + K . Entonces, la cantidad max(A) – min(A) es al menos ans = (max(A) – K) – (min(A) + K) .
Podemos alcanzar este valor, mediante las siguientes modificaciones:
 

• Si A[i] <= min(A) + K, entonces A[i] = min(A) + K
• De lo contrario, si A[i] >= max(A) – K, entonces A[i] = max(A) – K

Si ans < 0 , la mejor respuesta que podríamos tener es ans = 0 , también usando la misma modificación. 
 

A continuación se muestra la implementación del enfoque anterior. 
 

// C++ program to find the minimum difference.
#include <bits/stdc++.h>
using namespace std;
 
// Function to return required minimum difference
int minDiff(int n, int x, int A[])
{
    int mn = A[0], mx = A[0];
 
    // finding minimum and maximum values
    for (int i = 0; i < n; ++i) {
        mn = min(mn, A[i]);
        mx = max(mx, A[i]);
    }
 
    // returning minimum possible difference
    return max(0, mx - mn - 2 * x);
}
 
// Driver program
int main()
{
 
    int n = 3, x = 3;
    int A[] = { 1, 3, 6 };
 
    // function to return the answer
    cout << minDiff(n, x, A);
 
    return 0;
}

// Java program to find the minimum difference.
 
import java.util.*;
class GFG
{
     
    // Function to return required minimum difference
    static int minDiff(int n, int x, int A[])
    {
        int mn = A[0], mx = A[0];
     
        // finding minimum and maximum values
        for (int i = 0; i < n; ++i) {
            mn = Math.min(mn, A[i]);
            mx = Math.max(mx, A[i]);
        }
     
        // returning minimum possible difference
        return Math.max(0, mx - mn - 2 * x);
    }
     
    // Driver program
    public static void main(String []args)
    {
     
        int n = 3, x = 3;
        int A[] = { 1, 3, 6 };
     
        // function to return the answer
        System.out.println(minDiff(n, x, A));
     
         
    }
 
}
 
// This code is contributed by ihritik

# Python program to find the minimum difference.
 
     
# Function to return required minimum difference
def minDiff( n,  x,  A):
  
    mn =  A[0]
    mx =  A[0]
 
    # finding minimum and maximum values
    for i in range(0,n):
         mn = min( mn,  A[ i])
         mx = max( mx,  A[ i])
      
 
    # returning minimum possible difference
    return max(0,  mx -  mn - 2 *  x)
  
     
# Driver program
 
n = 3
x = 3
A = [1, 3, 6 ]
 
# function to return the answer
print(minDiff( n,  x,  A))
 
# This code is contributed by ihritik

// C# program to find the minimum difference.
 
using System;
class GFG
{
     
    // Function to return required minimum difference
    static int minDiff(int n, int x, int []A)
    {
        int mn = A[0], mx = A[0];
     
        // finding minimum and maximum values
        for (int i = 0; i < n; ++i) {
            mn = Math.Min(mn, A[i]);
            mx = Math.Max(mx, A[i]);
        }
     
        // returning minimum possible difference
        return Math.Max(0, mx - mn - 2 * x);
    }
     
    // Driver program
    public static void Main()
    {
     
        int n = 3, x = 3;
        int []A = { 1, 3, 6 };
     
        // function to return the answer
        Console.WriteLine(minDiff(n, x, A));
            
    }
}
 
// This code is contributed by ihritik

<?php
 
// PHP program to find the minimum difference.
 
     
// Function to return required minimum difference
function minDiff($n, $x, $A)
{
    $mn = $A[0];
    $mx = $A[0];
 
    // finding minimum and maximum values
    for ($i = 0; $i < $n; ++$i) {
        $mn = min($mn, $A[$i]);
        $mx = max($mx, $A[$i]);
    }
 
    // returning minimum possible difference
    return max(0, $mx - $mn - 2 * $x);
}
     
// Driver program
 
$n = 3;
$x = 3;
$A = array( 1, 3, 6 );
 
// function to return the answer
echo minDiff($n, $x, $A);
 
// This code is contributed by ihritik
 
?>

<script>
 
// JavaScript program to find the minimum difference.
 
// Function to return required minimum difference
function  minDiff( n,  x, A)
{
    var mn = A[0], mx = A[0];
 
    // finding minimum and maximum values
    for (var i = 0; i < n; ++i) {
        mn = Math.min(mn, A[i]);
        mx = Math.max(mx, A[i]);
    }
 
    // returning minimum possible difference
    return Math.max(0, mx - mn - 2 * x);
}
 
var n = 3, x = 3;
var A = [ 1, 3, 6 ];
 
// function to return the answer
document.write( minDiff(n, x, A));
 
// This code is contributed by SoumikMondal
 
</script>

0

Complejidad de tiempo: O(n)