Suma de las primeras M fracciones formadas a partir de una array de números primos

Dado un entero M y una array de enteros ordenados arr [] de longitud N que contiene 1 y N-1 números primos , cada uno de los cuales aparece solo una vez, la tarea es encontrar la suma de las M fracciones más pequeñas posibles formadas a partir de los elementos de array dados donde cada fracción es de la forma arr[i]/arr[j] ( i < j ).

Nota: Devuelva la respuesta redondeada a 6 dígitos después del decimal.

Ejemplos:

Entrada: arr[] = {1, 2, 3, 5}, M = 2 
Salida: 0,533333 
Explicación : todas las fracciones posibles son: {1/2, 1/3, 1/5, 2/3, 2/5, 3/5} 
Después de ordenar, todas las fracciones posibles son {1/5, 1/3, 2/5, 1/2, 3/5, 2/3},
por lo que la suma de la primera M (aquí 2) será 1/5+ 1/3 = 8/15 = 0,533333

Entrada: arr[] = {7, 9, 11}, M = 1
Salida: 0.636364
Explicación: Todas las fracciones posibles son – {7/9, 7/11, 9/11}
después de ordenar todas las fracciones posibles son {7/11 , 7/9, 9/11}
por lo que la suma de la primera M (aquí 1) será 7/11 = 0,636364

Enfoque ingenuo: una idea básica es encontrar todas las fracciones posibles formadas por los elementos de la array y ordenarlas. Luego devuelva la suma de los primeros M elementos más pequeños.

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(N) 

Enfoque eficiente: un enfoque eficiente para resolver este problema será usar el montón mínimo. La siguiente es la idea detrás de eso:

La mínima fracción posible asociada a cada elemento será la de mayor denominador. Así que será de la forma arr[i]/arr[N-1]. Cualquier fracción asociada con cualquier valor de array (arr[i]) será mayor que esto. 
En base a esto, podemos resolver el problema con la ayuda de min heap como se muestra aquí:

• Inicialmente, coloque todas las fracciones que tengan el valor arr[i]/arr[N-1] en el montón, luego extraiga el valor mínimo y busque la siguiente fracción mayor asociada con su numerador (si el valor era arr[i]/arr[j] la siguiente fracción mayor asociada con arr[i] será arr[i]/arr[j-1]). 
• Ponga esta fracción en el montón mínimo. 
• Luego, encuentre nuevamente el mínimo de los elementos en el montón y repita lo mismo hasta que no se seleccionen M elementos.

Siga la ilustración a continuación para una mejor comprensión.

Ilustración:

Considere: arr[] = {1, 2, 3, 5}, M = 2

Inicialmente coloque todas las fracciones mínimas posibles asociadas con cada elemento de la array. 
Elemento de montón de la forma { valor de fracción, índice de numerador, índice de denominador }:
        -> montón = { {0.2, 0, 3}, {0.4, 1, 3}, {0.6, 2, 3} }

1ª Iteración:
        -> Valor mínimo 0.2.
        -> Suma = 0 + 0,2 = 0,2.
        -> Pop el valor mínimo. montón { {0.4, 1, 3}, {0.6, 2, 3} }.
        -> La siguiente fracción mayor asociada con 1 es 1/3 = 0.333333.
        -> montón = { {0.333333, 0, 2}, {0.4, 1, 3}, {0.6, 2, 3} }.
        -> M = 2-1 = 1.

2ª Iteración:
        -> Valor mínimo 0,333333.
        -> Suma = 0,2 + 0,333333 = 0,533333.
        -> Pop el valor mínimo. montón = { {0.4, 1, 3}, {0.6, 2, 3} }.
        -> La siguiente fracción mayor asociada con 1 es 1/2 = 0.5.
        -> montón = { {0.4, 1, 3}, {0.5, 0, 1}, {0.6, 2, 3} }.
        -> M = 1-1 = 0.

Entonces la suma es 0.533333

Siga los pasos mencionados a continuación para implementar la idea:

• Cree un montón mínimo para almacenar el valor de las fracciones y los índices del numerador y el denominador.
• Inicialmente agregue las fracciones mínimas posibles al montón mínimo.
• Bucle hasta que M sea mayor que 0 :
  • Haga estallar el elemento superior y agréguelo a la suma de la fracción.
  • Encuentre la siguiente fracción mayor asociada con su numerador como se mencionó anteriormente.
  • Empuje esa fracción en el montón mínimo.
  • Disminuya M en 1 .
• Devuelve el valor de la suma como la respuesta.

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

// C++ program to implement above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Structure for storing fractions and index
struct fractionElement {
 
    // For storing fractional value
    double value;
    int i, j;
    fractionElement(double d, int x, int y)
        : value(d), i(x), j(y)
    {
    }
    bool operator<(const fractionElement& f) const
    {
        return value > f.value;
    }
};
 
// Function for getting sum of
// M smallest fraction
double SumofMfractions(vector<int>& A, int M)
{
    // Creating a priority_queue based upon
    // our structure
    priority_queue<fractionElement> pq;
 
    for (int i = 0; i < A.size(); i++) {
 
        // Pushing element in priority_queue
        // keeping the last index as same
        pq.push(fractionElement((double)(A[i])
                                    / A.back(),
                                i, A.size() - 1));
    }
    double sum = 0;
 
    while (M > 1) {
        auto top = pq.top();
 
        // Pop up the top element
        pq.pop();
 
        // Adding the value to the sum
        sum += top.value;
        top.j--;
 
        // Decreasing the last index to get
        // other value pair of i, j
        pq.push(fractionElement(
            (double)(A[top.i]) / A[top.j],
            top.i, top.j));
 
        M--;
    }
 
    // Adding latest top value
    sum += pq.top().value;
 
    // returning the sum of m smallest fractions
    return sum;
}
 
// Driver code
int main()
{
    vector<int> A = { 1, 2, 3, 5 };
    int M = 2;
 
    // Function call
    cout << SumofMfractions(A, M) << endl;
    return 0;
}

// Java code to implement the approach
import java.io.*;
import java.util.*;
 
class GFG {
    // Structure for storing fractions and index
    static class fractionElement
        implements Comparable<fractionElement> {
        // For storing fractional value
        double value;
        int i, j;
        fractionElement(double d, int x, int y)
        {
            value = d;
            i = x;
            j = y;
        }
        public int compareTo(fractionElement o)
        {
            if (value > o.value)
                return 1;
            else if (value < o.value)
                return -1;
            return 0;
        }
    }
 
    // Function for getting sum of
    // M smallest fraction
    static double SumofMfractions(int[] A, int M)
    {
        // Creating a priority_queue based upon
        // our structure
        PriorityQueue<fractionElement> pq
            = new PriorityQueue<>();
 
        for (int i = 0; i < A.length; i++) {
 
            // Pushing element in priority_queue
            // keeping the last index as same
            pq.add(new fractionElement(
                (double)(A[i]) / A[A.length - 1], i,
                A.length - 1));
        }
        double sum = 0;
 
        while (M > 1) {
            fractionElement top = pq.peek();
 
            // Pop up the top element
            pq.remove();
 
            // Adding the value to the sum
            sum += top.value;
            top.j--;
 
            // Decreasing the last index to get
            // other value pair of i, j
            pq.add(new fractionElement((double)(A[top.i])
                                           / A[top.j],
                                       top.i, top.j));
 
            M--;
        }
 
        // Adding latest top value
        sum += pq.peek().value;
 
        // returning the sum of m smallest fractions
        return sum;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int[] A = { 1, 2, 3, 5 };
        int M = 2;
        // Function call
        System.out.println(SumofMfractions(A, M));
    }
}
// This code is contributed by Karandeep1234

0.533333

Complejidad de Tiempo: O(M * logN)
Espacio Auxiliar: O(N)