Battalions and tanks

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
2 upvotes
Asked in companies
HSBCAmazon

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3 6
1000 2000 10000
3 12
4 8 12
Sample output 1 :
2500.000000
2.000000
Explanation of Sample output 1 :
For the first test case, we can distribute the tanks such that the first battalion gets 1 tank, the second battalion gets 1 tank, and the third battalion gets 4 tanks. In this way the ratio of soldiers in a battalion to the number of tanks allotted will be [1000, 2000, 2500] where the maximum ratio is 2500. This is the optimal distribution, and no other distribution can generate a smaller value of the maximum ratio.

For the second test case, [2, 4, 6] distribution will lead to a minimum value of maximum ratio which is 2.
Sample Input 2 :
2
3 3
2 5 7
1 4
8
Sample output 2 :
7.000000
2.000000
Explanation of Sample output 2 :
For the first test case, there are only 3 tanks available so we will distribute 1 tank to each battalion.

For the second test case, there is only 1 battalion so assign all tanks to that battalion.
Hint

Can you think of using a max-heap for this task?

Approaches (2)
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:

  1. Let us create a max-heap of pair<int, int> 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.
  2. 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’
  3. 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.
  4. Get the top-most element of max-heap which will be the battalion with the maximum ratio.

 

Time Complexity

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)).

Space Complexity

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).

Code Solution
(100% EXP penalty)
Battalions and tanks
Full screen
Console