Dada una array[] de enteros, la tarea es encontrar el número mínimo de operaciones requeridas para cambiar los elementos de la array de modo que para cualquier entero positivo M , |arr[i] – M| ≤ 1 para todos los i válidos .
En una sola operación, cualquier elemento de la array puede incrementarse o disminuirse en 1.
Ejemplos:
Entrada: arr[] = {10, 1, 4}
Salida: 7
Si cambiamos 1 a 2 y 10 a 4 con el conteo de operaciones siendo |1 – 2| + |10 – 4| = 7
Después de cambiar, la array se convierte en {4, 2, 4} donde la diferencia absoluta de cada elemento con M = 3 es ≤ 1
Entrada: arr[] = {5, 7, 4, 1, 4}
Salida: 4
Enfoque: comenzando desde el elemento mínimo de la array hasta el elemento máximo de la array, digamos num , calcule el recuento de operaciones necesarias para cambiar cada elemento de modo que su diferencia absoluta con num sea ≤ 1 . El mínimo entre todas las operaciones posibles es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the minimum
// number of operations required
int changeTheArray(int arr[], int n)
{
// Minimum and maximum elements from the array
int minEle = *(std::min_element(arr, arr + n));
int maxEle = *(std::max_element(arr, arr + n));
// To store the minimum number of
// operations required
int minOperations = INT_MAX;
for (int num = minEle; num <= maxEle; num++) {
// To store the number of operations required
// to change every element to either
// (num - 1), num or (num + 1)
int operations = 0;
for (int i = 0; i < n; i++) {
// If current element is not already num
if (arr[i] != num) {
// Add the count of operations
// required to change arr[i]
operations += (abs(num - arr[i]) - 1);
}
}
// Update the minimum operations so far
minOperations = min(minOperations, operations);
}
return minOperations;
}
// Driver code
int main()
{
int arr[] = { 10, 1, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << changeTheArray(arr, n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG {
// Function to return the minimum
// number of operations required
static int changeTheArray(int arr[], int n)
{
// Minimum and maximum elements from the array
int minEle = Arrays.stream(arr).min().getAsInt();
int maxEle = Arrays.stream(arr).max().getAsInt();
// To store the minimum number of
// operations required
int minOperations = Integer.MAX_VALUE;
for (int num = minEle; num <= maxEle; num++) {
// To store the number of operations required
// to change every element to either
// (num - 1), num or (num + 1)
int operations = 0;
for (int i = 0; i < n; i++) {
// If current element is not already num
if (arr[i] != num) {
// Add the count of operations
// required to change arr[i]
operations += (Math.abs(num - arr[i]) - 1);
}
}
// Update the minimum operations so far
minOperations = Math.min(minOperations, operations);
}
return minOperations;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 10, 1, 4 };
int n = arr.length;
System.out.println(changeTheArray(arr, n));
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python3 implementation of the approach import math import sys # Function to return the minimum # number of operations required def changeTheArray(arr, n): # Minimum and maximum elements # from the array minEle = min(arr) maxEle = max(arr) # To store the minimum number of # operations required minOperations = sys.maxsize for num in range(minEle, maxEle + 1): # To store the number of operations required # to change every element to either # (num - 1), num or (num + 1) operations = 0 for i in range(n): # If current element is not already num if arr[i] != num: operations += (abs(num - arr[i]) - 1) # Update the minimum operations so far minOperations = min(minOperations, operations) return minOperations # Driver code if __name__=='__main__': arr = [10, 1, 4] n = len(arr) print(changeTheArray(arr, n)) # This code is contributed by Vikash Kumar 37
C#
// C# implementation of the approach
using System;
using System.Linq;
class GFG
{
// Function to return the minimum
// number of operations required
static int changeTheArray(int []arr, int n)
{
// Minimum and maximum elements from the array
int minEle = arr.Min();
int maxEle = arr.Max();
// To store the minimum number of
// operations required
int minOperations = int.MaxValue;
for (int num = minEle; num <= maxEle; num++)
{
// To store the number of operations required
// to change every element to either
// (num - 1), num or (num + 1)
int operations = 0;
for (int i = 0; i < n; i++)
{
// If current element is not already num
if (arr[i] != num)
{
// Add the count of operations
// required to change arr[i]
operations += (Math.Abs(num - arr[i]) - 1);
}
}
// Update the minimum operations so far
minOperations = Math.Min(minOperations, operations);
}
return minOperations;
}
// Driver code
public static void Main(String []args)
{
int []arr = { 10, 1, 4 };
int n = arr.Length;
Console.WriteLine(changeTheArray(arr, n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of the approach
// Function to return the minimum
// number of operations required
function changeTheArray(arr, n)
{
// Minimum and maximum elements from the array
let minEle = Math.min(...arr);
let maxEle = Math.max(...arr);
// To store the minimum number of
// operations required
let minOperations = Number.MAX_VALUE;
for (let num = minEle; num <= maxEle; num++) {
// To store the number of operations required
// to change every element to either
// (num - 1), num or (num + 1)
let operations = 0;
for (let i = 0; i < n; i++) {
// If current element is not already num
if (arr[i] != num) {
// Add the count of operations
// required to change arr[i]
operations += (Math.abs(num - arr[i]) - 1);
}
}
// Update the minimum operations so far
minOperations = Math.min(minOperations, operations);
}
return minOperations;
}
// Driver code
let arr = [ 10, 1, 4 ];
let n = arr.length;
document.write(changeTheArray(arr, n));
</script>
Producción:
7
Complejidad de Tiempo: O((maxEle-minEle)*n)
Espacio Auxiliar: O(1), ya que no se ha tomado ningún espacio extra.