Battalions and tanks
Let there be ‘N’ battalions of soldiers and ‘M’ tanks. You are also given an array/list of length ‘N’ whose i-th index denotes the number of soldiers in the i-th battalion. You are supposed to divide the ‘M’ tanks to ‘N’ battalions such that the maximum ratio of soldiers in a battalion to the number of tanks allotted to that battalion is minimised.

You can assume that the number of tanks is always greater than the number of battalions.

Input Format :

The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows. The first input line of each test case contains two integers ‘N’ and ‘M’ denoting the number of battalions and tanks respectively. The second line of each test case contains ‘N’ space-separated integers denoting the number of soldiers in ‘N’ battalions.

Output Format :

For each test case, return the maximum ratio of soldiers in a battalion to the number of tanks as described in the problem statement. Your answer is considered correct if its absolute or relative error doesn't exceed 0.000001.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints :

1

Question

Battalions and tanks

Let there be ‘N’ battalions of soldiers and ‘M’ tanks. You are also given an array/list of length ‘N’ whose i-th index denotes the number of soldiers in the i-th battalion. You are supposed to divide the ‘M’ tanks to ‘N’ battalions such that the maximum ratio of soldiers in a battalion to the number of tanks allotted to that battalion is minimised.

You can assume that the number of tanks is always greater than the number of battalions.

Input Format :

The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first input line of each test case contains two integers ‘N’ and ‘M’ denoting the number of battalions and tanks respectively.

The second line of each test case contains ‘N’ space-separated integers denoting the number of soldiers in ‘N’ battalions.

Output Format :

For each test case, return the maximum ratio of soldiers in a battalion to the number of tanks as described in the problem statement.

Your answer is considered correct if its absolute or relative error doesn't exceed 0.000001.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 50
1 <= ‘N’ <= 1000
‘N’ <= ‘M’ <= 10000
1 <= ARR[i] <= 1000000

Time limit: 1 sec

Accepted Answer

Max-heap based approach.

Let us first assign 1 tank to each battalion because the number of tanks assigned to any battalion will definitely be greater than or equal to 1. Now, if any extra tank is left then assigning the tank to the battalion having the maximum ratio of soldiers to the number of tanks will be an optimal choice. Because the maximum ratio will definitely decrease if we assign the next tank to this battalion. Similarly, we can do it for each remaining tank.

We can observe here that at each instance we are supposed to find the battalion having the maximum ratio. We can easily perform this task using a max-heap.

Consider the following steps:

Let us create a max-heap of pair where the first integer denotes the number of soldiers in the battalion and the second integer denotes the number of tanks assigned to that battalion. We will have to write a custom comparator for this max-heap such that the battalion with the maximum ratio is always at the top.
Now, let us assign a tank to each battalion and insert the pair of index and tank in the max-heap. And decrement the count of remaining tanks i.e. ‘M’ = ‘M’ - ‘N’
Now, for each remaining tank:
- Get the top-most element of max-heap which will be the battalion with the maximum ratio.
- Assign the current tank to this battalion i.e. increment the count of tanks allotted.
- Insert the updated battalion information in the max-heap.
Get the top-most element of max-heap which will be the battalion with the maximum ratio.

Space Complexity: O(n)Explanation:

O(N), Where ‘N’ denotes the number of battalions.

Since we are using a max-heap to store the information of each battalion which takes O(N) space. So the overall space complexity will be O(N).

Time Complexity: OtherExplanation:

O(M * log(N)), Where ‘N’ and ‘M’ denotes the number of battalions and tanks respectively.

Since we are using a max-heap where insert and extract maximum operation takes O(log(N)) time (‘N’ is the number of elements in the heap). And in this approach, we are performing an insert and an extract maximum operation for each tank. So the overall complexity will be O(M * log(N)).

Python (3.5)

'''

    Time Complexity : O(M * log(N))

    Space Complexity : O(N)

    

    Where 'N' and 'M' denotes the number of battalions and tanks respectively.

'''



import heapq



# Custom comparator for max-heap.

class compare:

    def __init__(self, pair: tuple):

        self.pair = pair



    def __lt__(self, other):

        return self.pair[0] * other.pair[1] > other.pair[0] * self.pair[1]





def getMinimumRatio(arr, n, m):



    # Max-heap which stores the number of tanks alloted to any battalion.

    maxHeap = []



    # Assign a tank to each battalion.

    for i in range(n):

        pair = (arr[i], 1)

        maxHeap.append(compare(pair))



    heapq.heapify(maxHeap)



    # Decrement the count of remaining tanks.

    m = m - n



    for i in range(1, m + 1):



        # Get the top-most element of max-heap which will be the battalion with the maximum ratio.

        u = heapq.heappop(maxHeap)



        # Assign the current tank to this battalion i.e. increment the count of tanks allotted.

        p = (u.pair[0], u.pair[1] + 1)



        # Insert the updated battalion information in the max-heap.

        heapq.heappush(maxHeap, compare(p))



    # Get the top-most element of max-heap which will be the battalion with the maximum ratio.

    u = heapq.heappop(maxHeap)



    # Return the ratio.

    return u.pair[0] / u.pair[1]

Java (SE 1.8)

/*
    Time Complexity : O(M * log(N))
    Space Complexity : O(N)
    
    Where 'N' and 'M' denotes the number of battalions and tanks respectively.
*/

import javafx.util.Pair;
import java.util.*;

public class Solution 
{
	// Custom comparator for max-heap.
	public static Comparator< Pair > customComparator = new Comparator< Pair>() {
	    public int compare(Pair< Integer, Integer > a, Pair< Integer, Integer > b) {
	        return a.getValue() * b.getKey() - a.getKey() * b.getValue();
	    }
	};

    public static double getMinimumRatio(ArrayList battalion, int n, int m) 
    {
        // Max-heap which stores the number of tanks alloted to any battalion.
		PriorityQueue < Pair > maxHeap = new PriorityQueue < Pair > (customComparator);

		// Assign a tank to each battalion.
		for (int i = 0; i < n; i++)
		{
			maxHeap.add(new Pair < Integer, Integer > (battalion.get(i), 1));
		}

		// Decrement the count of remaining tanks.
		m = m - n;

		for (int i = 1; i <= m; i++)
		{
			// Get the top-most element of max-heap which will be the battalion with the maximum ratio.
			Pair < Integer, Integer > topElement = maxHeap.peek(); 
			maxHeap.remove();

			// Assign the current tank to this battalion i.e. increment the count of tanks allotted.
			Pair < Integer, Integer > u = new Pair < Integer, Integer > (topElement.getKey(), topElement.getValue()+1);

			// Insert the updated battalion information in the max-heap.
			maxHeap.add(u);
		}

		// Get the top-most element of max-heap which will be the battalion with the maximum ratio.
		Pair < Integer, Integer > u = maxHeap.peek();

		// Return the ratio.
		return ((double)u.getKey() / (double)u.getValue());
    }
}

C++ (g++ 5.4)

/*
    Time Complexity : O(M * log(N))
    Space Complexity : O(N)
    
    Where 'N' and 'M' denotes the number of battalions and tanks respectively.
*/

#include 

// Custom comparator for max-heap.
class compare
{
public:
	bool operator()(pair &a, pair &b)
	{
		return a.first * b.second < a.second * b.first;
	}
};

double getMinimumRatio(vector &battalion, int n, int m)
{
	// Max-heap which stores the number of tanks alloted to any battalion.
	priority_queue, vector>, compare> maxHeap;

	// Assign a tank to each battalion.
	for (int i = 0; i < n; i++)
	{
		maxHeap.push({battalion[i], 1});
	}

	// Decrement the count of remaining tanks.
	m = m - n;

	for (int i = 1; i <= m; i++)
	{
		// Get the top-most element of max-heap which will be the battalion with the maximum ratio.
		pair u = maxHeap.top();
		maxHeap.pop();

		// Assign the current tank to this battalion i.e. increment the count of tanks allotted.
		u.second++;

		// Insert the updated battalion information in the max-heap.
		maxHeap.push(u);
	}

	// Get the top-most element of max-heap which will be the battalion with the maximum ratio.
	pair u = maxHeap.top();

	// Return the ratio.
	return ((double)u.first / (double)u.second);
}

Accepted Answer

Binary search based approach.

The basic idea of this approach is to find the minimum ratio using a binary search.

Let us see how to check if a given real number (say ‘X’) is the minimum ratio(as defined in the problem statement) or not.

We will iterate through each battalion and allot a minimum number of tanks to each battalion such that the ratio of the number of soldiers to the number of tanks allotted is less than or equal to ‘X’. Now, if the sum of total allotted tanks exceeds the number of tanks given then, the minimum ratio must be greater than the chosen ‘X’. Otherwise, the minimum ratio will be either ‘X’ or less than ‘X’.

Consider the following steps:

Initialize the search space for the minimum ratio . ‘l’ = 0.0 and ‘r’ = 10^6. Maximum possible value can be estimated by the maximum possible number of soldiers in any battalion.
Now, loop until (r - l) > 0.000001. Because it is given that the answer will be correct if the absolute error is less than or equal to 0.000001.
- Assign ‘MID’ = l + (r - l)/2.0
- Now, initialize a variable ‘COUNT’ to zero which stores the ‘COUNT’ of tanks allotted to all the battalions.
- Iterate through the battalions and allot a minimum number of tanks to each battalion such that the ratio of the number of soldiers to the number of tanks allotted is less than equal to the 'MID'. Also add the number of allotted tanks to ‘COUNT’.
- Now, if ‘COUNT’ > ‘M’ then, update the ‘l’ to 'MID'. Because the minimum ratio will be definitely greater than 'MID'.
- Otherwise, update the ‘r’ to 'MID'. Because the minimum ratio will be definitely less than or equal to 'MID'.

Space Complexity: O(1)Explanation:

O(1)

Since we are not using any extra space, the overall space complexity will be O(1).

Time Complexity: OtherExplanation:

O(N * log(10^12)), Where ‘N’ is the number of battalions.

Since we are doing a binary search where our length of the search space is reduced by half each time and also we need to ensure the relative error. And at each iteration, we are traversing through the array/list of battalions. So the overall time complexity will be O(N * log(10^12)).