Dada una array arr[] y un entero K , esa tarea es elegir como máximo K elementos de la array y reemplazarlos por cualquier número. Encuentre la diferencia mínima entre el valor máximo y mínimo de la array después de realizar como máximo el reemplazo de K.
Ejemplos:
Entrada: arr[] = {1, 4, 6, 11, 15}, k = 3
Salida: 2
Explicación:
k = 1, arr = {4, 4, 6, 11, 15}, arr[0] reemplazado por 4
k = 2, arr = {4, 4, 6, 4, 15}, arr[3] reemplazado por 4
k = 3, arr = {4, 4, 6, 4, 4}, arr[4] reemplazado por 4
Máx – Mín = 6 – 4 = 2Entrada: arr[] = {1, 4, 6, 11, 15}, k = 2
Salida: 5
Explicación:
k = 1, arr = {1, 4, 6, 6, 15}, arr[3] reemplazado por 6
k = 2, arr = {1, 4, 6, 6, 6}, arr[4] reemplazado por 6
Max – Min = 6 – 1 = 5
Enfoque: La idea es utilizar el concepto de Two Pointers . A continuación se muestran los pasos:
- Ordenar la array dada.
- Mantenga dos punteros, uno apuntando al último elemento de la array y el otro al K -ésimo elemento de la array.
- Itere sobre la array K + 1 veces y cada vez encuentre la diferencia de los elementos señalados por los dos punteros.
- Cada vez que encuentre la diferencia, realice un seguimiento de la diferencia mínima posible en una variable y devuelva ese valor al final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum difference
// between the maximum and the minimum
// elements arr[] by at most K replacements
int maxMinDifference(int arr[], int n, int k)
{
// Check if turns are more than
// or equal to n-1 then simply
// return zero
if (k >= n - 1)
return 0;
// Sort the array
sort(arr, arr + n);
// Set difference as the
// maximum possible difference
int ans = arr[n - 1] - arr[0];
// Iterate over the array to
// track the minimum difference
// in k turns
for (int i = k, j = n - 1;
i >= 0; --i, --j) {
ans = min(arr[j] - arr[i], ans);
}
// Return the answer
return ans;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 4, 6, 11, 15 };
int N = sizeof(arr) / sizeof(arr[0]);
// Given K replacements
int K = 3;
// Function Call
cout << maxMinDifference(arr, N, K);
return 0;
}
Java
// Java program of the approach
import java.io.*;
import java.util.Arrays;
class GFG{
// Function to find minimum difference
// between the maximum and the minimum
// elements arr[] by at most K replacements
static int maxMinDifference(int arr[], int n, int k)
{
// Check if turns are more than
// or equal to n-1 then simply
// return zero
if (k >= n - 1)
return 0;
// Sort the array
Arrays.sort(arr);
// Set difference as the
// maximum possible difference
int ans = arr[n - 1] - arr[0];
// Iterate over the array to
// track the minimum difference
// in k turns
for (int i = k, j = n - 1;
i >= 0; --i, --j)
{
ans = Math.min(arr[j] - arr[i], ans);
}
// Return the answer
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 1, 4, 6, 11, 15 };
int N = arr.length;
// Given K replacements
int K = 3;
// Function Call
System.out.print(maxMinDifference(arr, N, K));
}
}
// This code is contributed by shivanisinghss2110
Python3
# Python3 program for the above approach # Function to find minimum difference # between the maximum and the minimum # elements arr[] by at most K replacements def maxMinDifference(arr, n, k): # Check if turns are more than # or equal to n-1 then simply # return zero if(k >= n - 1): return 0 # Sort the array arr.sort() # Set difference as the # maximum possible difference ans = arr[n - 1] - arr[0] # Iterate over the array to # track the minimum difference # in k turns i = k j = n - 1 while i >= 0: ans = min(arr[j] - arr[i], ans) i -= 1 j -= 1 # Return the answer return ans # Driver code if __name__ == '__main__': # Given array arr[] arr = [ 1, 4, 6, 11, 15 ] N = len(arr) # Given K replacements K = 3 # Function Call print(maxMinDifference(arr, N, K)) # This code is contributed by Shivam Singh
C#
// C# program of the approach
using System;
class GFG{
// Function to find minimum difference
// between the maximum and the minimum
// elements arr[] by at most K replacements
static int maxMinDifference(int []arr, int n, int k)
{
// Check if turns are more than
// or equal to n-1 then simply
// return zero
if (k >= n - 1)
return 0;
// Sort the array
Array.Sort(arr);
// Set difference as the
// maximum possible difference
int ans = arr[n - 1] - arr[0];
// Iterate over the array to
// track the minimum difference
// in k turns
for (int i = k, j = n - 1;
i >= 0; --i, --j)
{
ans = Math.Min(arr[j] - arr[i], ans);
}
// Return the answer
return ans;
}
// Driver Code
public static void Main(string[] args)
{
// Given array arr[]
int [] arr = new int[] { 1, 4, 6, 11, 15 };
int N = arr.Length;
// Given K replacements
int K = 3;
// Function Call
Console.Write(maxMinDifference(arr, N, K));
}
}
// This code is contributed by Ritik Bansal
Javascript
<script>
// Javascript program for the above approach
// Function to find minimum difference
// between the maximum and the minimum
// elements arr[] by at most K replacements
function maxMinDifference(arr, n, k)
{
// Check if turns are more than
// or equal to n-1 then simply
// return zero
if (k >= n - 1)
return 0;
// Sort the array
arr.sort((a, b) => a - b);
// Set difference as the
// maximum possible difference
let ans = arr[n - 1] - arr[0];
// Iterate over the array to
// track the minimum difference
// in k turns
for (let i = k, j = n - 1;
i >= 0; --i, --j)
{
ans = Math.min(arr[j] - arr[i], ans);
}
// Return the answer
return ans;
}
// Driver Code
// Given array arr[]
let arr = [ 1, 4, 6, 11, 15 ];
let N = arr.length;
// Given K replacements
let K = 3;
// Function Call
document.write(maxMinDifference(arr, N, K));
</script>
Producción:
2
Complejidad de tiempo: O(N*log 2 N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por sayantanpal1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA