Diferencia mínima entre el valor máximo y mínimo de Array con Operaciones dadas

Dada una array arr[] y un entero K . Las siguientes operaciones se pueden realizar en cualquier elemento de la array: 
 

1. Multiplique el elemento de la array con K .
2. 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: 
 

1. 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.
2. 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.
3. Actualice la respuesta si la diferencia actual es menor que la calculada hasta ahora.
4. Esto continúa hasta que quedan elementos en el conjunto múltiple.

A continuación se muestra la implementación del enfoque anterior: 
 

// 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 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 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# 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.

<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>

5

Complejidad de tiempo: O (NlogN)