Mithlesh has ‘N’ buckets each consisting of some fruits. Mithlesh 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’.
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. Mithlesh 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 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 Mithlesh 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: Print the required marker. Sample Input 1: 4 30 10 40 30 20 Sample Output 1: 20 We have 4 buckets each having 10, 40, 30, and 20 fruits respectively. And, Mithlesh wants to eat at least 30 fruits. Now, if we set our marker at 20 then Mithlesh 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. Sample Input 2: 4 16 5 8 20 1 Sample Output 2: 6 In the second test case, if we set the marker at 6 then Mithlesh can eat following fruits from each bucket: 0 (1st bucket) + 2 (2nd bucket) + 14 (bucket) + 0 (4th bucket) = 16 (K)
Method 1(Brute Force):
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 Mithlesh 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 Mithlesh 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 Mithlesh wants to eat) then return count.
Implementation in C++:
#include <bits/stdc++.h>
using namespace std;
int getMaxMarker(vector<int>& arr, int N, int M)
{
// Find the maximum element in the array
int maxx = *(max_element(arr.begin(), arr.end()));
int ans = 0;
// Iterate over the range 0 to maxx
for (int i = maxx; i >= 0; i--) {
// Variable to store the number of fruits that
// Mithlesh can eat if the marker is at 'i'.
int count = 0;
// Iterate over the arr to calculate the number of
// fruits in each bucket that Mithlesh can eat.
for (int j = 0; j < N; j++) {
if (arr[j] - i > 0)
count += arr[j] - i;
}
// If, Mithlesh can eat 'M' (required fruits) then
// take 'i' as the answer and stops further
// iterations.
if (count >= M) {
ans = i;
break;
}
}
return ans;
}
int main()
{
vector<int> arr{ 10, 40, 30, 20 };
int n = 4, m = 30;
cout << getMaxMarker(arr, n, m) << endl;
return 0;
}
Output:
20
Time Complexity: O(N * X), where ‘N’ is the total number of buckets and ‘X’ is the maximum number of fruits in any particular bucket.
Since we are just searching for the marker in range “maxx” to 0 and running a loop on all the buckets, so the overall time complexity will be O(N * X).
Space Complexity: O(1).
Method 2(Using Binary Search):
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 Mithlesh 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 Mithlesh has to eat at least M fruits.
Implementation in C++:
#include <bits/stdc++.h>
using namespace std;
int getMaxMarker(vector<int>& arr, int N, int M)
{
// Find the maximum element in the array
int maxx = *(max_element(arr.begin(), arr.end()));
int left = 0, right = maxx;
while (left < right) {
// Calculate the mid value of left and right
int mid = (left + right + 1) / 2;
// Variable to store the number of fruits that
// Mithlesh can eat if the marker is at 'i'.
int count = 0;
// Iterate over the arr to calculate the number of
// fruits in each bucket that Mithlesh can eat.
for (int i = 0; i < N; i++) {
if (arr[i] - mid > 0)
count += arr[i] - mid;
}
// If, Mithlesh can eat 'M' (required fruits) then
// take 'i' as the answer and stops further
// iterations.
if (count == M)
return mid;
else if (count < M)
right = mid - 1;
else
left = mid;
}
return left;
}
int main()
{
vector<int> arr{ 10, 40, 30, 20 };
int n = 4, m = 30;
cout << getMaxMarker(arr, n, m) << endl;
return 0;
}
Output:
20
Time Complexity: O(N * log(X)), where ‘N’ is the total number of buckets and ‘X’ is the maximum number of fruits in any particular bucket.
Since we are just searching for the marker in range 0 to “maxx” and running a loop on all the buckets, so the overall time complexity will be O(N * log(X)).
Space Complexity: O(1).