Dada una array A[] que consiste en números enteros positivos, la tarea es calcular la desviación mínima posible de la array dada A[] después de realizar las siguientes operaciones cualquier número de veces:
- Operación 1: si el elemento del arreglo es par , divídelo entre 2 .
- Operación 2: Si el elemento del arreglo es impar , multiplícalo por 2 .
La desviación de la array A[] es la diferencia entre el elemento máximo y mínimo presente en la array A[] .
Ejemplos:
Entrada: A[] = {4, 1, 5, 20, 3}
Salida: 3
Explicación: la array se modifica a {4, 2, 5, 5, 3} después de realizar las operaciones dadas. Por lo tanto, desviación = 5 – 2 = 3.Entrada : A[] = {1, 2, 3, 4}
Salida : 1
Explicación: la array se modifica después de dos operaciones a {2, 2, 3, 2}. Por lo tanto, desviación = 3 – 2 = 1.
Enfoque: El problema se puede resolver con base en las siguientes observaciones:
- Los números pares se pueden dividir varias veces hasta que se convierte en un número impar.
- Los números impares se pueden duplicar solo una vez, ya que se convierte en un número par.
- Por lo tanto, los números pares nunca se pueden aumentar.
Siga los pasos a continuación para resolver el problema:
- Atraviese la array y duplique todos los elementos impares de la array. Esto anula el requisito de la 2ª operación.
- Ahora, disminuya el elemento de array más grande mientras sea par.
- Para almacenar los elementos de la array de manera ordenada, inserte todos los elementos de la array en un Set .
- Reducir con avidez el máximo elemento presente en el Conjunto
- Si el elemento máximo presente en el Conjunto es impar, rompa el ciclo .
- Imprime la desviación mínima obtenida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the
// above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum
// deviation of the array A[]
void minimumDeviation(int A[], int N)
{
// Store all array elements
// in sorted order
set<int> s;
for (int i = 0; i < N; i++) {
if (A[i] % 2 == 0)
s.insert(A[i]);
// Odd number are transformed
// using 2nd operation
else
s.insert(2 * A[i]);
}
// (Maximum - Minimum)
int diff = *s.rbegin() - *s.begin();
// Check if the size of set is > 0 and
// the maximum element is divisible by 2
while ((int)s.size()
&& *s.rbegin() % 2 == 0) {
// Maximum element of the set
int maxEl = *s.rbegin();
// Erase the maximum element
s.erase(maxEl);
// Using operation 1
s.insert(maxEl / 2);
// (Maximum - Minimum)
diff = min(diff, *s.rbegin() - *s.begin());
}
// Print the Minimum
// Deviation Obtained
cout << diff;
}
// Driver Code
int main()
{
int A[] = { 4, 1, 5, 20, 3 };
int N = sizeof(A) / sizeof(A[0]);
// Function Call to find
// Minimum Deviation of A[]
minimumDeviation(A, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG
{
// Function to find the minimum
// deviation of the array A[]
static void minimumDeviation(int A[], int N)
{
// Store all array elements
// in sorted order
TreeSet<Integer> s = new TreeSet<Integer>();
for (int i = 0; i < N; i++)
{
if (A[i] % 2 == 0)
s.add(A[i]);
// Odd number are transformed
// using 2nd operation
else
s.add(2 * A[i]);
}
// (Maximum - Minimum)
int diff = s.last() - s.first() ;
// Check if the size of set is > 0 and
// the maximum element is divisible by 2
while ((s.last() % 2 == 0))
{
// Maximum element of the set
int maxEl = s.last();
// Erase the maximum element
s.remove(maxEl);
// Using operation 1
s.add(maxEl / 2);
// (Maximum - Minimum)
diff = Math.min(diff, s.last() - s.first());
}
// Print the Minimum
// Deviation Obtained
System.out.print(diff);
}
// Driver code
public static void main(String[] args)
{
int A[] = { 4, 1, 5, 20, 3 };
int N = A.length;
// Function Call to find
// Minimum Deviation of A[]
minimumDeviation(A, N);
}
}
// This code is contributed by susmitakundugoaldanga.
Python3
# Python 3 implementation of the # above approach # Function to find the minimum # deviation of the array A[] def minimumDeviation(A, N): # Store all array elements # in sorted order s = set([]) for i in range(N): if (A[i] % 2 == 0): s.add(A[i]) # Odd number are transformed # using 2nd operation else: s.add(2 * A[i]) # (Maximum - Minimum) s = list(s) diff = s[-1] - s[0] # Check if the size of set is > 0 and # the maximum element is divisible by 2 while (len(s) and s[-1] % 2 == 0): # Maximum element of the set maxEl = s[-1] # Erase the maximum element s.remove(maxEl) # Using operation 1 s.append(maxEl // 2) # (Maximum - Minimum) diff = min(diff, s[-1] - s[0]) # Print the Minimum # Deviation Obtained print(diff) # Driver Code if __name__ == "__main__": A = [4, 1, 5, 20, 3] N = len(A) # Function Call to find # Minimum Deviation of A[] minimumDeviation(A, N) # This code is contributed by chitranayal.
C#
// C# implementation of the
// above approach
using System;
using System.Collections.Generic;
using System.Linq;
class GFG
{
// Function to find the minimum
// deviation of the array A[]
static void minimumDeviation(int[] A, int N)
{
// Store all array elements
// in sorted order
HashSet<int> s = new HashSet<int>();
for (int i = 0; i < N; i++)
{
if (A[i] % 2 == 0)
s.Add(A[i]);
// Odd number are transformed
// using 2nd operation
else
s.Add(2 * A[i]);
}
List<int> S = s.ToList();
S.Sort();
// (Maximum - Minimum)
int diff = S[S.Count - 1] - S[0];
// Check if the size of set is > 0 and
// the maximum element is divisible by 2
while ((int)S.Count != 0 && S[S.Count - 1] % 2 == 0) {
// Maximum element of the set
int maxEl = S[S.Count - 1];
// Erase the maximum element
S.RemoveAt(S.Count - 1);
// Using operation 1
S.Add(maxEl / 2);
S.Sort();
// (Maximum - Minimum)
diff = Math.Min(diff, S[S.Count - 1] - S[0]);
}
// Print the Minimum
// Deviation Obtained
Console.Write(diff);
}
// Driver code
static void Main()
{
int[] A = { 4, 1, 5, 20, 3 };
int N = A.Length;
// Function Call to find
// Minimum Deviation of A[]
minimumDeviation(A, N);
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// JavaScript implementation of the
// above approach
// Function to find the minimum
// deviation of the array A[]
function minimumDeviation(A, N)
{
// Store all array elements
// in sorted order
var s = new Set();
for (var i = 0; i < N; i++) {
if (A[i] % 2 == 0)
s.add(A[i]);
// Odd number are transformed
// using 2nd operation
else
s.add(2 * A[i]);
}
var tmp = [...s].sort((a,b)=>a-b);
// (Maximum - Minimum)
var diff = tmp[tmp.length-1] - tmp[0];
// Check if the size of set is > 0 and
// the maximum element is divisible by 2
while (s.size
&& tmp[tmp.length-1] % 2 == 0) {
// Maximum element of the set
var maxEl = tmp[tmp.length-1];
// Erase the maximum element
s.delete(maxEl);
// Using operation 1
s.add(parseInt(maxEl / 2));
tmp = [...s].sort((a,b)=>a-b);
// (Maximum - Minimum)
diff = Math.min(diff, tmp[tmp.length-1] - tmp[0]);
}
// Print the Minimum
// Deviation Obtained
document.write( diff);
}
// Driver Code
var A = [4, 1, 5, 20, 3];
var N = A.length;
// Function Call to find
// Minimum Deviation of A[]
minimumDeviation(A, N);
</script>
Producción:
3
Complejidad de tiempo : O(N * log(N))
Espacio auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por saikumarkudikala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA