Dada una array arr[] y un entero K . Las siguientes operaciones se pueden realizar en cualquier elemento de la array:
- Multiplique el elemento de la array con K .
- Si el elemento es divisible por K , entonces divídalo por K .
Las dos operaciones anteriores se pueden aplicar cualquier número de veces, incluido el cero, en cualquier elemento de la array. La tarea es encontrar la mínima diferencia posible entre el valor máximo y mínimo de la array.
Ejemplos:
Entrada: arr[] = {1, 5000, 9999}, K = 10000
Salida: 5000
Explicación:
La diferencia mínima posible entre el elemento máximo y el elemento mínimo es 5000. Cuando el elemento 1 se multiplica por K, el elemento máximo de la array se convierte en 10000 y el elemento mínimo es 5000. Y este es el valor mínimo posible.
Entrada: arr[] = {1, 2, 3, 4, 5, 10, 7}, K = 5
Salida: 5
Explicación:
En el primer paso, los elementos 5 y 10 se pueden dividir con 5 convirtiéndolo en 1 y 2 respectivamente.
En el segundo paso, 1 se puede multiplicar por 5. Esto hace que 2 sea el elemento mínimo y 7 el elemento máximo en la array. Por lo tanto, la diferencia es 5.
Enfoque: La idea es utilizar Priority Queue como un Multiset . Se pueden seguir los siguientes pasos para calcular la respuesta:
- Inicialmente, todos los valores posibles (es decir, el valor obtenido cuando el elemento de la array se multiplica por K, dividido por K) se insertan en el conjunto múltiple junto con los índices.
- Valores emergentes continuos del conjunto múltiple. En cada instancia, el valor emergente X con índice i es el máximo y si al menos un valor ha sido extraído para todos los índices, la respuesta actual será X – min de (máximo de valores previamente extraídos para un índice ) para todos los índices excepto i.
- Actualice la respuesta si la diferencia actual es menor que la calculada hasta ahora.
- Esto continúa hasta que quedan elementos en el conjunto múltiple.
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 calculate Minimum
// difference between maximum and
// minimum value of the array
int calculateMinDiff(int arr[], int k , int n)
{
// Variable to store minimum difference
int ans = INT_MAX;
// PriorityQueue which is used as a multiset
// to store all possible values
priority_queue< pair<int,int> > pq;
// Iterate through all the values and
// add it to the priority queue
for (int i = 0; i < n; i++)
{
// If the number is divisible by k
// divide it by K and add to priority queue
if (arr[i] % k == 0)
pq.push(make_pair( arr[i] / k, i ));
// Adding number as it is
pq.push(make_pair( arr[i], i ));
// Adding number after multiplying it by k
pq.push(make_pair(arr[i] * k, i ));
}
// HashMap to keep track of current values
map<int ,int>mp;
while (!pq.empty())
{
pair<int,int>temp = pq.top();
pq.pop();
mp.insert(temp);
// if for every index there is at-least
// 1 value we calculate the answer
if (mp.size() == n)
{
int min_value = INT_MAX;
for(auto x:mp)
min_value=min(min_value, x.second);
ans = min(ans, temp.first - min_value);
}
}
// Returning the calculated answer
return ans;
}
// Driver code
int main()
{
// Input Array
int arr[7] = { 1, 2, 3, 4, 5, 10, 7 };
int K = 5;
// Size of the array
int N = sizeof(arr)/sizeof(int);
// Printing final output
cout << (calculateMinDiff(arr, K, N));
}
// This code is contributed by ishayadav2918
Java
// Java implementation of the above approach
import java.io.*;
import java.util.*;
class GfG {
// Function to calculate Minimum
// difference between maximum and
// minimum value of the array
private static int calculateMinDiff(int arr[], int k)
{
// Length of the array
int n = arr.length;
// Variable to store minimum difference
int ans = Integer.MAX_VALUE;
// PriorityQueue which is used as a multiset
// to store all possible values
PriorityQueue<int[]> pq
= new PriorityQueue<>((int x[], int y[]) -> x[0] - y[0]);
// Iterate through all the values and
// add it to the priority queue
for (int i = 0; i < n; i++) {
// If the number is divisible by k
// divide it by K and add to priority queue
if (arr[i] % k == 0)
pq.add(new int[] { arr[i] / k, i });
// Adding number as it is
pq.add(new int[] { arr[i], i });
// Adding number after multiplying it by k
pq.add(new int[] { arr[i] * k, i });
}
// HashMap to keep track of current values
HashMap<Integer, Integer> map = new HashMap<>();
while (!pq.isEmpty()) {
int temp[] = pq.poll();
map.put(temp[1], temp[0]);
// if for every index there is at-least
// 1 value we calculate the answer
if (map.size() == n) {
ans = Math.min(ans,
temp[0]
- Collections.min(map.values()));
}
}
// Returning the calculated answer
return ans;
}
// Driver code
public static void main(String args[])
{
// Input Array
int arr[] = { 1, 2, 3, 4, 5, 10, 7 };
int K = 5;
// Printing final output
System.out.println(calculateMinDiff(arr, K));
}
}
Python3
# Python3 implementation of the above approach
import sys
# Function to calculate Minimum
# difference between maximum and
# minimum value of the array
def calculateMinDiff(arr, k , n) :
# Variable to store minimum difference
ans = sys.maxsize
# PriorityQueue which is used as a multiset
# to store all possible values
pq = []
# Iterate through all the values and
# add it to the priority queue
for i in range(n) :
# If the number is divisible by k
# divide it by K and add to priority queue
if (arr[i] % k == 0) :
pq.append((arr[i] // k, i ))
# Adding number as it is
pq.append((arr[i], i))
# Adding number after multiplying it by k
pq.append((arr[i] * k, i))
pq.sort()
pq.reverse()
# HashMap to keep track of current values
mp = {}
while (len(pq) > 0) :
temp = pq[0]
pq.pop(0)
mp[temp[0]] = temp[1]
# if for every index there is at-least
# 1 value we calculate the answer
if (len(mp) == n) :
min_value = sys.maxsize
for x in mp :
min_value = min(min_value, mp[x])
ans = min(ans, temp[0] - min_value - 1)
# Returning the calculated answer
return ans
# Input Array
arr = [ 1, 2, 3, 4, 5, 10, 7 ]
K = 5
# Size of the array
N = len(arr)
# Printing final output
print(calculateMinDiff(arr, K, N))
# This code is contributed by divyesh072019.
C#
// C# implementation of the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to calculate Minimum
// difference between maximum and
// minimum value of the array
static int calculateMinDiff(int[] arr, int k , int n)
{
// Variable to store minimum difference
int ans = Int32.MaxValue;
// PriorityQueue which is used as a multiset
// to store all possible values
List<Tuple<int,int>> pq = new List<Tuple<int,int>>();
// Iterate through all the values and
// add it to the priority queue
for (int i = 0; i < n; i++)
{
// If the number is divisible by k
// divide it by K and add to priority queue
if (arr[i] % k == 0)
pq.Add(new Tuple<int,int>( arr[i] / k, i ));
// Adding number as it is
pq.Add(new Tuple<int,int>( arr[i], i ));
// Adding number after multiplying it by k
pq.Add(new Tuple<int,int>(arr[i] * k, i ));
}
pq.Sort();
pq.Reverse();
// HashMap to keep track of current values
Dictionary<int, int> mp = new Dictionary<int, int>();
while (pq.Count > 0)
{
Tuple<int,int> temp = pq[0];
pq.RemoveAt(0);
mp[temp.Item1] = temp.Item2;
// if for every index there is at-least
// 1 value we calculate the answer
if (mp.Count == n)
{
int min_value = Int32.MaxValue;
foreach(KeyValuePair<int, int> x in mp)
{
min_value=Math.Min(min_value, x.Value);
}
ans = Math.Min(ans, temp.Item1 - min_value - 1);
}
}
// Returning the calculated answer
return ans;
}
// Driver code
static void Main()
{
// Input Array
int[] arr = { 1, 2, 3, 4, 5, 10, 7 };
int K = 5;
// Size of the array
int N = arr.Length;
// Printing final output
Console.WriteLine(calculateMinDiff(arr, K, N));
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// JavaScript implementation of the above approach
// Function to calculate Minimum
// difference between maximum and
// minimum value of the array
function calculateMinDiff(arr, k, n) {
// Variable to store minimum difference
let ans = Number.MAX_SAFE_INTEGER;
// PriorityQueue which is used as a multiset
// to store all possible values
let pq = new Array();
// Iterate through all the values and
// push it to the priority queue
for (let i = 0; i < n; i++) {
// If the number is divisible by k
// divide it by K and push to priority queue
if (arr[i] % k == 0)
pq.push(new Array(Math.floor(arr[i] / k), i));
// pushing number as it is
pq.push(new Array(arr[i], i));
// pushing number after multiplying it by k
pq.push(new Array(arr[i] * k, i));
}
pq.sort((a, b) => a[0] - b[0]);
pq.reverse();
// HashMap to keep track of current values
let mp = new Map();
while (pq.length > 0) {
let temp = pq[0];
pq.shift();
mp.set(temp[0], temp[1]);
// if for every index there is at-least
// 1 value we calculate the answer
if (mp.size == n) {
let min_value = Number.MAX_SAFE_INTEGER;
for (let x of mp) {
min_value = Math.min(min_value, x[1]);
}
ans = Math.min(ans, temp[1] - min_value);
}
}
// Returning the calculated answer
return ans;
}
// Driver code
// Input Array
let arr = [1, 2, 3, 4, 5, 10, 7];
let K = 5;
// Size of the array
let N = arr.length;
// Printing final output
document.write(calculateMinDiff(arr, K, N));
// This code is contributed by gfgking
</script>
Producción:
5
Complejidad de tiempo: O (NlogN)
Publicación traducida automáticamente
Artículo escrito por ishan_trivedi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA