Given a positive integer K and an array arr[] consisting of {numerator, denominator} of N fractions, the task is to find the sum of the ratio of the given fractions after incrementing numerators and denominators by 1, K number of times.
Examples:
Input: arr[][] = {{1, 2}, {3, 5}, {2, 2}}, K = 2
Output: 0.78333
Explanation:
The most optimal choice is to increment the first fraction K(= 2) number of times. Therefore, the sum of ratio is (3/4 + 3/5 + 2/2) / 3 = 0.78333, which is maximum possible.Input: arr[][] = {{1, 1}, {4, 5}}, K = 5
Output: 0.95
Approach: The given problem can be solved by using the Greedy Approach, the idea is to increment that fraction among the given fractions whose increment maximizes the sum of ratios of fractions. This idea can be implemented using the priority queue. Follow the below steps to solve the problem:
- Initialize a Max Heap, say PQ using the priority queue which stores the value that will be incremented in the total average ratio if an operation is performed on ith index for all values of i in the range [0, N).
- Insert all the indexes of the fraction in the array arr[] in the priority queue PQ with the incremented value of fractions.
- Iterate over the range [0, K – 1] and perform the following steps:
- Pop the top element of the PQ.
- Increment the fraction of the current popped index.
- Insert all the current fractions in the array arr[] in the priority queue PQ with the incremented value of fractions.
- After completing the above steps, print the sum of ratios of all the fractions stored in priority_queue PQ.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to increment the K fractions// from the given array to maximize the// sum of ratios of the given fractionsdouble maxAverageRatio( vector<vector<int> >& arr, int K){ // Size of the array int N = arr.size(); // Max priority queue priority_queue<pair<double, int> > q; // Iterate through the array for (int i = 0; i < N; i++) { // Insert the incremented value // if an operation is performed // on the ith index double extra = (((double)arr[i][0] + 1) / ((double)arr[i][1] + 1)) - ((double)arr[i][0] / (double)arr[i][1]); q.push(make_pair(extra, i)); } // Loop to perform K operations while (K--) { int i = q.top().second; q.pop(); // Increment the numerator and // denominator of ith fraction arr[i][0] += 1; arr[i][1] += 1; // Add the incremented value double extra = (((double)arr[i][0] + 1) / ((double)arr[i][1] + 1)) - ((double)arr[i][0] / (double)arr[i][1]); q.push(make_pair(extra, i)); } // Stores the average ratio double ans = 0; for (int i = 0; i < N; i++) { ans += ((double)arr[i][0] / (double)arr[i][1]); } // Return the ratio return ans / N;}// Driver Codeint main(){ vector<vector<int> > arr = { { 1, 2 }, { 3, 5 }, { 2, 2 } }; int K = 2; cout << maxAverageRatio(arr, K); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class Pair<K, V> { private final K key; private final V value; public Pair(K key, V value) { this.key = key; this.value = value; } public K getKey() { return key; } public V getValue() { return value; }}class GFG { // Function to increment the K fractions // from the given array to maximize the // sum of ratios of the given fractions static double maxAverageRatio(int[][] arr, int K) { // Size of the array int N = arr.length; // Max priority queue PriorityQueue<Pair<Double, Integer> > q = new PriorityQueue<>( new Comparator<Pair<Double, Integer> >() { @Override public int compare( Pair<Double, Integer> a, Pair<Double, Integer> b) { return b.getKey().compareTo( a.getKey()); } }); // Iterate through the array for (int i = 0; i < N; i++) { // Insert the incremented value // if an operation is performed // on the ith index double extra = (((double)arr[i][0] + 1) / ((double)arr[i][1] + 1)) - ((double)arr[i][0] / (double)arr[i][1]); q.offer(new Pair<>(extra, i)); } // Loop to perform K operations while (K-- > 0) { int i = q.poll().getValue(); // Increment the numerator and // denominator of ith fraction arr[i][0] += 1; arr[i][1] += 1; // Add the incremented value double extra = (((double)arr[i][0] + 1) / ((double)arr[i][1] + 1)) - ((double)arr[i][0] / (double)arr[i][1]); q.offer(new Pair<>(extra, i)); } // Stores the average ratio double ans = 0; for (int i = 0; i < N; i++) { ans += ((double)arr[i][0] / (double)arr[i][1]); } // Return the ratio return ans / N; } public static void main(String[] args) { int[][] arr = { { 1, 2 }, { 3, 5 }, { 2, 2 } }; int K = 2; System.out.printf("%.6f", maxAverageRatio(arr, K)); }}// This code is contributed by lokesh. |
Python3
# Python program for the above approach# Function to increment the K fractions# from the given array to maximize the# sum of ratios of the given fractionsdef maxAverageRatio(arr,k): #Size of the array N=len(arr) # Max priority queue q=[] # Iterate through the array for i in range(N): # Insert the incremented value # if an operation is performed # on the ith index extra = ((float(arr[i][0])+1)/(float(arr[i][1])+1))-(float(arr[i][0])/float(arr[i][1])) q.append([extra,i]) # Loop to perform K operations while(k>0): k=k-1 i=q[0][1] q.pop(0) # Increment the numerator and # denominator of ith fraction arr[i][0]=arr[i][0]+1 arr[i][1]=arr[i][1]+1 # Add the incremented value extra = ((float(arr[i][0])+1)/(float(arr[i][1])+1))-(float(arr[i][0])/float(arr[i][1])) q.append([extra,i]) # Stores the average ratio ans=0 for i in range(N): ans=ans+(float(arr[i][0])/float(arr[i][1])) # Return the ratio return ans/N# Driver Codearr = [ [ 1, 2 ], [ 3, 5 ], [ 2, 2 ] ]K = 2print(maxAverageRatio(arr, K))# This code is contributed by Pushpesh Raj |
C#
// C# program for the above approachusing System;using System.Linq;using System.Collections.Generic;class GFG { // Structure to store a fraction private struct Fraction { public int Numerator; public int Denominator; } // Function to increment the K fractions // from the given array to maximize the // sum of ratios of the given fractions static double MaxAverageRatio(Fraction[] arr, int K) { // Size of the array int N = arr.Length; // Array to store extra value after incrementing // each fraction double[] extra = new double[N]; // Iterate through the array for (int i = 0; i < N; i++) { // Calculate extra value after incrementing // fraction extra[i] = ((double)(arr[i].Numerator + 1) / (double)(arr[i].Denominator + 1)) - (double)arr[i].Numerator / (double)arr[i].Denominator; } // Loop to perform K operations while (K-- > 0) { // Find the index of fraction with the maximum // extra value int index = Array.IndexOf(extra, extra.Max()); // Increment the numerator and denominator of // fraction arr[index].Numerator += 1; arr[index].Denominator += 1; // Calculate new extra value for the fraction extra[index] = ((double)(arr[index].Numerator + 1) / (double)(arr[index].Denominator + 1)) - (double)arr[index].Numerator / (double)arr[index].Denominator; } // Stores the average ratio double ans = 0; for (int i = 0; i < N; i++) { ans += (double)arr[i].Numerator / (double)arr[i].Denominator; } // Return the ratio return ans / N; } static void Main(string[] args) { Fraction[] arr = new Fraction[] { new Fraction{ Numerator = 1, Denominator = 2 }, new Fraction{ Numerator = 3, Denominator = 5 }, new Fraction{ Numerator = 2, Denominator = 2 } }; int K = 2; Console.WriteLine("{0:0.000000}", MaxAverageRatio(arr, K)); }}// This code is contributed by phasing17. |
Javascript
<script>// Javascript program for the above approach// Function to increment the K fractions// from the given array to maximize the// sum of ratios of the given fractionsfunction maxAverageRatio(arr, K){ // Size of the array var N = arr.length; // Max priority queue var q = []; // Iterate through the array for (var i = 0; i < N; i++) { // Insert the incremented value // if an operation is performed // on the ith index var extra = ((arr[i][0] + 1) / (arr[i][1] + 1)) - (arr[i][0] / arr[i][1]); q.push([extra, i]); } q.sort(); // Loop to perform K operations while (K--) { var i = q[q.length-1][1]; q.pop(); // Increment the numerator and // denominator of ith fraction arr[i][0] += 1; arr[i][1] += 1; // Add the incremented value var extra = ((arr[i][0] + 1) / (arr[i][1] + 1)) - (arr[i][0] / arr[i][1]); q.push([extra, i]); q.sort(); } // Stores the average ratio var ans = 0; for (var i = 0; i < N; i++) { ans += (arr[i][0] / arr[i][1]); } // Return the ratio return ans / N;}// Driver Codevar arr = [[1, 2 ], [3, 5], [2, 2 ]];var K = 2;document.write(maxAverageRatio(arr, K).toFixed(6));// This code is contributed by rrrtnx.</script> |
Output:
0.783333
Time Complexity: O(K*log N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
