Dada una array arr[] que consta de N enteros positivos, la tarea es minimizar la diferencia máxima entre cualquier par de elementos de la array multiplicando cualquier elemento impar de la array por 2 y dividiendo cualquier elemento par de la array por 2 .
Ejemplos:
Entrada: arr[] = {4, 1, 5, 20, 3}
Salida: 3
Explicación:
Operación 1: Multiplicar arr[1] por 2 modifica arr[] a {4, 2, 5, 20, 3}.
Operación 2: Dividir arr[3] por 2 modifica arr[] a {4, 2, 5, 10, 3}.
Operación 3: Dividir arr[3] por 2 modifica arr[] a {4, 2, 5, 5, 3}.
Por lo tanto, el mínimo de la diferencia máxima de cualquier par en la array = 5 – 2 = 3.Entrada: arr[] = {1, 2, 5, 9}
Salida: 7
Explicación:
Operación 1: Multiplicar arr[0] por 2 modifica arr[] a { 2, 2, 5, 9 }
Operación 2: Multiplicar arr[ 2] por 2 modifica arr[] a {2, 2, 10, 9 }
Por lo tanto, el mínimo de la diferencia máxima de cualquier par en la array = 9 – 2 = 7.
Enfoque: siga los pasos a continuación para resolver el problema dado:
- Primero, inserte todos los elementos de la array en un Set S . Si el elemento de la array es par , insértelo tal cual. De lo contrario, conviértelo en par multiplicándolo por 2 .
- Almacene la diferencia entre el último y el primer elemento en el Conjunto S en una variable, digamos res .
- Recorre el conjunto S en el orden inverso y haz lo siguiente:
- Actualice el valor de res al máximo de res y la diferencia entre el primer elemento y el actual del conjunto.
- Elimina el elemento actual del Conjunto.
- Insertar (elemento actual) / 2 en el conjunto.
- Si el valor del elemento actual es impar, entonces ninguna array más elementos puede hacer que la diferencia máxima sea más pequeña. Por lo tanto salir del bucle .
- Después de completar los pasos anteriores, imprima el valor de res como la diferencia resultante.
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 minimize the maximum
// difference between any pair of elements
// of the array by the given operations
int minimumMaxDiff(vector<int>& nums)
{
set<int> s;
// Traverse the array
for (int i = 0; i < nums.size(); i++) {
// If current element is even
if (nums[i] % 2 == 0)
// Insert it into even
s.insert(nums[i]);
// Otherwise
else
// Make it even by multiplying
// by 2 and insert it into set
s.insert(nums[i] * 2);
}
// Calculate difference between first
// and the last element of the set
int res = *s.rbegin() - *s.begin();
// Iterate until difference is minimized
while (*s.rbegin() % 2 == 0) {
int x = *s.rbegin();
// Erase the current element
s.erase(x);
// Reduce current element by half
// and insert it into the Set
s.insert(x / 2);
// Update difference
res = min(res, *s.rbegin()
- *s.begin());
}
// Return the resultant difference
return res;
}
// Driver Code
int main()
{
vector<int> arr = { 1, 2, 5, 9 };
cout << minimumMaxDiff(arr);
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG
{
// Function to minimize the maximum
// difference between any pair of elements
// of the array by the given operations
static int minimumMaxDiff(int[] nums)
{
TreeSet<Integer> s = new TreeSet<Integer>();
// Traverse the array
for (int i = 0; i < nums.length; i++)
{
// If current element is even
if (nums[i] % 2 == 0)
// Insert it into even
s.add(nums[i]);
// Otherwise
else
// Make it even by multiplying
// by 2 and insert it into set
s.add(nums[i] * 2);
}
// Calculate difference between first
// and the last element of the set
int res = s.last() - s.first();
// Iterate until difference is minimized
while (s.last() % 2 == 0)
{
int x = s.last();
// Erase the current element
s.remove(x);
// Reduce current element by half
// and insert it into the Set
s.add(x / 2);
// Update difference
res = Math.min(res, s.last() - s.first());
}
// Return the resultant difference
return res;
}
// Driver code
public static void main(String[] args)
{
int[] arr = new int[] { 1, 2, 5, 9 };
System.out.print(minimumMaxDiff(arr));
}
}
// This code is contributed by jithin
Python3
# Python3 program for the above approach
# Function to minimize the maximum
# difference between any pair of elements
# of the array by the given operations
def minimumMaxDiff(nums):
s = {}
# Traverse the array
for i in range(len(nums)):
# If current element is even
if (nums[i] % 2 == 0):
# Insert it into even
s[nums[i]] = 1
# Otherwise
else:
# Make it even by multiplying
# by 2 and insert it into set
s[nums[i] * 2] = 1
# Calculate difference between first
# and the last element of the set
sr = list(s.keys())
res = sr[-1] - sr[0]
# Iterate until difference is minimized
while (list(s.keys())[-1] % 2 == 0):
r = list(s.keys())
x = r[-1]
# Erase the current element
del s[x]
# Reduce current element by half
# and insert it into the Set
s[x // 2] = 1
rr = list(s.keys())
# Update difference
res = min(res, rr[-1] - r[0])
# Return the resultant difference
return res
# Driver Code
if __name__ == '__main__':
arr = [ 1, 2, 5, 9 ]
print (minimumMaxDiff(arr))
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
using System.Linq;
class GFG
{
// Function to minimize the maximum
// difference between any pair of elements
// of the array by the given operations
static int minimumMaxDiff(int[] nums)
{
HashSet<int> s = new HashSet<int>();
// Traverse the array
for (int i = 0; i < nums.Length; i++) {
// If current element is even
if (nums[i] % 2 == 0)
// Insert it into even
s.Add(nums[i]);
// Otherwise
else
// Make it even by multiplying
// by 2 and insert it into set
s.Add(nums[i] * 2);
}
// Calculate difference between first
// and the last element of the set
int res = s.Last() - s.First();
// Iterate until difference is minimized
while (s.Last() % 2 == 0) {
int x = s.Last();
// Erase the current element
s.Remove(x);
// Reduce current element by half
// and insert it into the Set
s.Add(x / 2);
// Update difference
res = Math.Min(res, s.Last() - s.First());
}
// Return the resultant difference
return res;
}
// Driver code
static public void Main()
{
int[] arr = new int[] { 1, 2, 5, 9 };
Console.WriteLine(minimumMaxDiff(arr));
}
}
// This code is contributed by Dharanendra L V
Javascript
<script>
// JavaScript program for the above approach
// Function to minimize the maximum
// difference between any pair of elements
// of the array by the given operations
function minimumMaxDiff( nums)
{
var s = new Set();
// Traverse the array
for (var i = 0; i < nums.length; i++) {
// If current element is even
if (nums[i] % 2 == 0)
// Insert it into even
s.add(nums[i]);
// Otherwise
else
// Make it even by multiplying
// by 2 and insert it into set
s.add(nums[i] * 2);
}
// Calculate difference between first
// and the last element of the set
var tmp = [...s].sort((a,b)=>a-b)
var res = tmp[tmp.length-1] - tmp[0];
// Iterate until difference is minimized
while (tmp[tmp.length-1] % 2 == 0) {
var x = tmp[tmp.length-1];
// Erase the current element
s.delete(x);
// Reduce current element by half
// and insert it into the Set
s.add(parseInt(x / 2));
tmp = [...s].sort((a,b)=>a-b)
// Update difference
res = Math.min(res,tmp[tmp.length-1]
- tmp[0]);
}
// Return the resultant difference
return res;
}
// Driver Code
var arr = [1, 2, 5, 9];
document.write( minimumMaxDiff(arr));
</script>
Producción:
7
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por IshwarGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA