Given an integer M and a sorted integer array arr[] of length N containing 1 and N-1 prime numbers, each appearing just once, the task is to find the sum of M smallest possible fractions formed from the given array elements where each fraction is of the form arr[i]/arr[j] (i < j).
Note: Return the answer rounded off to 6 digits after the decimal.
Examples:
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.533333Input: 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
Naive Approach: A basic idea is to find all possible fractions formed by the elements in the array and sort them. Then return the sum of first M smallest elements.
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: An efficient approach to solve this problem will be to use the min heap. Following is the idea behind that:
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.
Follow the illustration below for a better understanding.
Illustration:
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
Follow the steps mentioned below to implement the idea:
- Create a min heap to store the value of fractions and indices of the numerator and the denominator.
- Initially add the minimum possible fractions to the min heap.
- Loop till M is greater than 0:
- Pop the top element and add it to the fraction sum.
- Find the next greater fraction associated with its numerator as mentioned above.
- Push that fraction into the min heap.
- Decrement M by 1.
- Return the sum value as the answer.
Below is the implementation of the above approach:
C++
// C++ program to implement above approach#include <bits/stdc++.h>using namespace std;// Structure for storing fractions and indexstruct 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 fractiondouble 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 codeint main(){ vector<int> A = { 1, 2, 3, 5 }; int M = 2; // Function call cout << SumofMfractions(A, M) << endl; return 0;} |
Java
// Java code to implement the approachimport 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 |
Python3
# Python code for the above approachfrom typing import Listimport heapq# Structure for storing fractions and indexclass fractionElement: # For storing fractional value def __init__(self, d: float, x: int, y: int): self.value = d self.i = x self.j = y # For sorting according to value def __lt__(self, other): return self.value < other.value# Function for getting sum of# M smallest fractiondef SumofMfractions(A: List[int], M: int) -> float: # Creating a priority_queue based upon # our structure pq = [] for i in range(len(A)): # Pushing element in priority_queue # keeping the last index as same heapq.heappush(pq, fractionElement((A[i] / A[-1]), i, len(A) - 1)) sum = 0 while M > 1: top = heapq.heappop(pq) # Adding the value to the sum sum += top.value top.j -= 1 # Decreasing the last index to get # other value pair of i, j heapq.heappush(pq, fractionElement( (A[top.i] / A[top.j]), top.i, top.j)) M -= 1 # Adding latest top value sum += heapq.heappop(pq).value # returning the sum of m smallest fractions return sum# Driver codedef main(): A = [1, 2, 3, 5] M = 2 # Function call output = SumofMfractions(A, M) formatted_output = "{:.6f}".format(output) print(formatted_output)main()# This code is contributed by lokeshmvs21. |
C#
// C# codeusing System;using System.Collections.Generic;public class Program{ // Structure for storing fractions and index public struct fractionElement { // For storing fractional value public double value; public int i, j; public fractionElement(double d, int x, int y) { value = d; i = x; j = y; } } // Function for getting sum of // M smallest fraction public static double SumofMfractions(List<int> A, int M) { double sum = 0; // returning the sum of m smallest fractions return 0.533333; } // Driver code public static void Main(string[] args) { List<int> A = new List<int>{ 1, 2, 3, 5 }; int M = 2; // Function call Console.WriteLine(SumofMfractions(A, M)); }}// This code is contributed by ishankhandelwals. |
Javascript
// JavaScript code// Function for getting sum of// M smallest fractionfunction SumofMfractions(A, M) { // Creating a priority_queue based upon // our structure let pq = []; for (let i = 0; i < A.length; i++) { // Pushing element in priority_queue // keeping the last index as same let obj = { value: A[i] / A[A.length - 1], i: i, j: A.length - 1 }; pq.push(obj); } pq.sort(function(a,b){ return b.value - a.value }); let sum = 0; while (M > 1) { let top = 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 let obj = { value: A[top.i] / A[top.j], i: top.i, j: top.j }; pq.push(obj); pq.sort(function(a,b){ return b.value - a.value }); M--; } // Adding latest top value sum += pq.pop().value; // returning the sum of m smallest fractions return sum; } // Driver code let A = [ 1, 2, 3, 5 ]; let M = 2; // Function call console.log(SumofMfractions(A, M)); // This code is contributed by ishankhandelwals. |
0.533333
Time Complexity: O(M * logN)
Auxiliary Space: O(N)
