Last Updated: 10 Feb, 2021

Kevin And His Fruits

Moderate

Asked in companies

Solve now

Problem statement

Kevin has ‘N’ buckets each consisting of some fruits. Kevin wants to eat at least ‘M’ fruits and so, he decided to set a marker (integer) as maximum as possible such that if he eats “number of fruits in the i-th bucket - marker” fruits then it must be at least ‘M’.

Example:

Let’s assume, we have 5 buckets each having 10, 40, 30, and 20 fruits respectively. And, Kevin wants to eat at least 30 fruits. 

Now, if we set our marker at 20 then Kevin can eat: (10 - 20) = -10 => 0 (fruit’s count can’t be negative) fruits from 1st bucket, (40 - 20) = 20 fruits from 2nd bucket, (30 - 20) = 10 fruits from the third bucket, and (20 - 20) = 0 fruits from the last bucket.

So, he can eat 0 + 20 + 10 + 0 = 30 fruits in total.

Note:

Each bucket may not have the same amount of fruits. It is guaranteed that the sum of all fruits (including all the buckets) will be greater than M. Kevin can only eat fruits from a particular bucket if and only if the bucket has more fruits than the marker.

Input Format:

The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain two space-separated integers ‘N’ and ‘M’ where ‘N’ is the total number of buckets, and ‘M’ is the minimum number of fruits that Kevin wants to eat.

The second line of each test case will contain ‘N’ space-separated integers which denote the number of fruits in the i-th bucket.

Output Format:

For each test case, print the required marker.

Output for every test case will be printed in a separate line.

Constraints:

1 <= T <= 10
1 <= N <= 10^4
1 <= M <= 10^6
0 <= ARR[i] <= 10^4

Where ‘T’ is the number of test cases.

Where 'N' is the number of buckets and ‘M’ is the integer representing the minimum number of fruits Kevin wants to eat. And, ARR[i] denotes the number of fruits in the i-th bucket.

Time limit: 1 sec

Solve now

Approaches

01 Approach

First, we should know that the marker can’t be negative and also it will not be greater than the maximum number of fruits in a particular bucket because if this happens then Kevin are not able to eat any of these fruits.

Therefore, the marker must be in the range of 0 to a maximum number of fruits in a particular bucket. So, the idea is to first calculate the maximum number of fruits in any particular bucket (say, maxx). After that, iterate over the range “maxx” to 0 and search for the maximum value of marker at which Kevin has to eat at least M fruits.

Algorithm:

Iterate over the array to find the max element, let’s name it “maxx”.
Now, iterate over the range of “maxx” to 0 (assume ‘i’ be the iterator)
Create a counter variable and initialize it with 0
Now, iterate over the given array (assume ‘j’ be the iterator)
- If, arr[j] - i > 0 then count += arr[j] - i
If, count >= M (minimum fruits that Kevin wants to eat) then return count.

Solve now

02 Approach

First, we should know that the marker can’t be negative and also it will not be greater than the maximum number of fruits in a particular bucket because if this happens then Kevin is not able to eat any of these fruits.

Therefore, the marker must be in the range of 0 to a maximum number of fruits in a particular bucket. So, the idea is to first calculate the maximum number of fruits in any particular bucket (say, maxx). After that, apply binary search in range 0 to maxx and search for the maximum value of marker at which Kevin has to eat at least M fruits.

Algorithm:

Iterate over the array to find the max element, let’s name it “maxx”.
Set the two pointers, “left” = 0 and “right” = maxx
Now, keep iterating while the left is less than the right
- Calculate the mid-value of left and right and store it in a variable called “mid”.
- Create a counter variable and initialize it with 0 which stores the number of fruits which can be eaten if the marker is set at “mid”.
- Now, iterate over the given array
  - If, arr[i] - mid > 0 then count += arr[i] - mid
  - Else, continue
- If, count = M (minimum fruits that Kevin wants to eat) return mid.
- Else if, count < M, then we will have to decrease the height of the marker to eat at least ‘M’ fruits. So, set “right” = “mid” - 1
- Else, “left” = “mid”
Return the value of left.

Solve now