Сумма первых M дробей, образованных из массива простых чисел

Даны целое число M и отсортированный целочисленный массив arr[] длины N , содержащий 1 и N-1 простых чисел, каждое из которых встречается только один раз, задача состоит в том, чтобы найти сумму M наименьших возможных дробей, образованных из заданных элементов массива, где каждая дробь имеет вид arr[i]/arr[j] ( i < j ).

Примечание. Округлите ответ до 6 знаков после запятой.

Примеры:

Input: arr[] = {1, 2, 3, 5}, M = 2 
Output: 0.533333 
Explanation: All possible fractions are – {1/2, 1/3, 1/5, 2/3, 2/5, 3/5} 
After sorting all possible fractions are {1/5, 1/3, 2/5, 1/2, 3/5, 2/3}
so sum of first M(here 2) will be 1/5+1/3 = 8/15 = 0.533333

Input: arr[] = {7, 9, 11}, M = 1
Output: 0.636364
Explanation: All possible fractions are – {7/9, 7/11, 9/11}
after sorting all possible fractions are  {7/11, 7/9, 9/11}
so sum of first M(here 1) will be 7/11 = 0.636364

Наивный подход: основная идея состоит в том, чтобы найти все возможные дроби, образованные элементами массива, и отсортировать их. Затем верните сумму первых M наименьших элементов.

Временная сложность: O(N ² )
Вспомогательное пространство: O(N)

Эффективный подход. Эффективным подходом к решению этой проблемы будет использование минимальной кучи. В основе этого лежит следующая идея:

The minimum possible fraction associated with each element will be the one with the highest denominator. So that will be of the form arr[i]/arr[N-1]. Any fraction associated with any array value (arr[i]) will be greater than this. 
Based of this we can solve the problem with the help of min heap as shown here:

• Initially put all fractions having value arr[i]/arr[N-1] into the heap, then pop the minimum value and find the next greater fraction associated with its numerator (If the value was arr[i]/arr[j] the next greater fraction associated with arr[i] will be arr[i]/arr[j-1]). 
• Put this fraction into the min heap. 
• Then again find the minimum from the elements in the heap and repeat the same till M elements are not selected.

Следуйте иллюстрации ниже для лучшего понимания.

Иллюстрация:

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

Initially put all the minimum possible fractions associated with each array element. 
Heap element of the form {fraction value, numerator index, denominator index}:
        -> heap = { {0.2, 0, 3}, {0.4, 1, 3}, {0.6, 2, 3} }

1st Iteration:
        -> Minimum value 0.2.
        -> Sum = 0 + 0.2 = 0.2.
        -> Pop the minimum value. heap { {0.4, 1, 3}, {0.6, 2, 3} }.
        -> Next greater fraction associated with 1 is 1/3 = 0.333333.
        -> heap = { {0.333333, 0, 2},  {0.4, 1, 3}, {0.6, 2, 3} }.
        -> M = 2-1 = 1.

2nd Iteration:
        -> Minimum value 0.333333.
        -> Sum = 0.2 + 0.333333 = 0.533333.
        -> Pop the minimum value. heap = { {0.4, 1, 3}, {0.6, 2, 3} }.
        -> Next greater fraction associated with 1 is 1/2 = 0.5.
        -> heap = { {0.4, 1, 3}, {0.5, 0, 1}, {0.6, 2, 3} }.
        -> M = 1-1 = 0.

So the sum is 0.533333

Следуйте шагам, указанным ниже, чтобы реализовать идею:

• Создайте мини-кучу для хранения значения дробей и индексов числителя и знаменателя.
• Изначально добавьте минимально возможные фракции в кучу min.
• Цикл до M больше 0 :
  • Вытащите верхний элемент и добавьте его к сумме дробей.
  • Найдите следующую большую дробь, связанную с ее числителем, как указано выше.
  • Поместите эту фракцию в кучу min.
  • Уменьшите М на 1 .
• Верните значение суммы в качестве ответа.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(M * logN)
Вспомогательное пространство: O(N)