Given N candies, M people, and an array arr[] of M positive integers, the task is to find the minimum value of K such that a Person A is able to consume the total of at least ceil of (N/(M + 1)) candies according to the following rules:
- In the first turn, Person A consumes a minimum of the number of candies left and K.
- In the next M turns, each ith Person over then range [0, M-1] consumes floor of arr[i] percentage of the remaining candies.
- Repeat the above steps, until no candies are left.
Examples:
Input: N = 13, M = 1, arr[] = {50}
Output: 3
Explanation:
For the value K as 3, the good share is the ceil of (13/2) = 7. Following are the turns that takes place:
- Person A takes min(3,13)=3 candies. Therefore, the candies left = 13 – 3 = 10.
- Person 0 takes arr[0](= 50)% of the 10 left candies, i.e., 5 candies. Therefore, the candies left = 10 – 5 = 5.
- Person A takes min(3,5)=3 candies. Therefore, the candies left = 5 – 3 = 2.
- Person 0 takes arr[0](= 50)% of the 2 left candies, i.e., 1 candies. Therefore, the candies left = 2 – 1 = 1.
- Person A takes 1 candy. Therefore, the candies left = 1 – 1 = 0.
After the above turns, the candies taken by the person is 3 + 3 + 1 = 7, which is at least (N/(M + 1)) candies, i.e., 13/2 = 6.
Input: N = 13, M = 2, arr[] = {40, 50}
Output: 2
Naive Approach: The simplest approach to solve the given problem is to check for each amount of candies Person A will get for all the possible values of K. Follow the below steps to solve this problem:
- Find the value of (N/(M + 1)) and stores it in a variable, say good as this is the minimum amount of candies Person A wants to take.
- Iterate over all the values of K in the range [1, N] and perform the following steps:
- For each value of K, simulate the process mentioned above and count the total number of candies Person A will get.
- If the amount of candies is at least the value of good, then break out of the loop. Otherwise, continue the iteration.
- After completing the above steps, print the current value of K as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find minimum value of// K such that the first person gets// at least (N/(M+1)) candiesvoid minimumK(vector<int> &arr, int M, int N){ // Find the minimum required value // of candies for the first person int good = ceil((N * 1.0) / ((M + 1) * 1.0)); // Iterate K from [1, n] for (int i = 1; i <= N; i++) { int K = i; // Total number of candies int candies = N; // Candies taken by Person 1 int taken = 0; while (candies > 0) { // Candies taken by 1st // person is minimum of K // and candies left taken += min(K, candies); candies -= min(K, candies); // Traverse the array arr[] for (int j = 0; j < M; j++) { // Amount consumed by the // person j int consume = (arr[j] * candies) / 100; // Update the number // of candies candies -= consume; } } // Good share of candies achieved if (taken >= good) { cout << i; return; } }}// Driver Codeint main(){ int N = 13, M = 1; vector<int> arr = { 50 }; minimumK(arr, M, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find minimum value of// K such that the first person gets// at least (N/(M+1)) candiesstatic void minimumK(ArrayList<Integer> arr, int M, int N){ // Find the minimum required value // of candies for the first person int good = (int)((N * 1.0) / ((M + 1) * 1.0)) + 1; // Iterate K from [1, n] for(int i = 1; i <= N; i++) { int K = i; // Total number of candies int candies = N; // Candies taken by Person 1 int taken = 0; while (candies > 0) { // Candies taken by 1st // person is minimum of K // and candies left taken += Math.min(K, candies); candies -= Math.min(K, candies); // Traverse the array arr[] for(int j = 0; j < M; j++) { // Amount consumed by the // person j int consume = (arr.get(j) * candies) / 100; // Update the number // of candies candies -= consume; } } // Good share of candies achieved if (taken >= good) { System.out.print(i); return; } }}// Driver Codepublic static void main(String[] args){ int N = 13, M = 1; ArrayList<Integer> arr = new ArrayList<Integer>(); arr.add(50); minimumK(arr, M, N);}}// This code is contributed by subhammahato348 |
Python3
# Python 3 program for the above approachimport math# Function to find minimum value of# K such that the first person gets# at least (N/(M+1)) candiesdef minimumK(arr, M, N): # Find the minimum required value # of candies for the first person good = math.ceil((N * 1.0) / ((M + 1) * 1.0)) # Iterate K from [1, n] for i in range(1, N + 1): K = i # Total number of candies candies = N # Candies taken by Person 1 taken = 0 while (candies > 0): # Candies taken by 1st # person is minimum of K # and candies left taken += min(K, candies) candies -= min(K, candies) # Traverse the array arr[] for j in range(M): # Amount consumed by the # person j consume = (arr[j] * candies) / 100 # Update the number # of candies candies -= consume # Good share of candies achieved if (taken >= good): print(i) return# Driver Codeif __name__ == "__main__": N = 13 M = 1 arr = [50] minimumK(arr, M, N) # This code is contributed by ukasp. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to find minimum value of// K such that the first person gets// at least (N/(M+1)) candiesstatic void minimumK(List<int> arr, int M, int N){ // Find the minimum required value // of candies for the first person int good = (int)((N * 1.0) / ((M + 1) * 1.0))+1; // Iterate K from [1, n] for (int i = 1; i <= N; i++) { int K = i; // Total number of candies int candies = N; // Candies taken by Person 1 int taken = 0; while (candies > 0) { // Candies taken by 1st // person is minimum of K // and candies left taken += Math.Min(K, candies); candies -= Math.Min(K, candies); // Traverse the array arr[] for (int j = 0; j < M; j++) { // Amount consumed by the // person j int consume = (arr[j] * candies) / 100; // Update the number // of candies candies -= consume; } } // Good share of candies achieved if (taken >= good) { Console.Write(i); return; } }}// Driver Codepublic static void Main(){ int N = 13, M = 1; List<int> arr = new List<int>(); arr.Add(50); minimumK(arr, M, N);}}// This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script>// JavaScript program for the above approach// Function to find minimum value of// K such that the first person gets// at least (N/(M+1)) candiesfunction minimumK(arr, M, N){ // Find the minimum required value // of candies for the first person let good = Math.floor((N * 1.0) / ((M + 1) * 1.0))+1; // Iterate K from [1, n] for (let i = 1; i <= N; i++) { let K = i; // Total number of candies let candies = N; // Candies taken by Person 1 let taken = 0; while (candies > 0) { // Candies taken by 1st // person is minimum of K // and candies left taken += Math.min(K, candies); candies -= Math.min(K, candies); // Traverse the array arr[] for (let j = 0; j < M; j++) { // Amount consumed by the // person j let consume = (arr[j] * candies) / 100; // Update the number // of candies candies -= consume; } } // Good share of candies achieved if (taken >= good) { document.write(i); return; } }}// Driver Code let N = 13, M = 1; let arr = new Array(); arr.push(50); minimumK(arr, M, N);// This code is contributed by _Saurabh_Jaiswal</script> |
Output:
3
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized by using Binary Search. Follow the steps below to solve the problem:
- Find the value of (N/(M + 1)) and stores it in a variable, say good as this is the minimum amount of candies Person A wants to take.
- Initialize two variables, say low and high as 1 and N respectively.
- Iterate until low is less than high and perform the following steps:
- Find the value of mid as (low + high)/2.
- Find the minimum number of candies taken by Person A for the value of K as mid by simulating the process mentioned above.
- If the number of candies taken by Person A is at least good then update the value of high as mid. Otherwise, update the value of low as (mid + 1).
- After completing the above steps, print the value of high as the resultant minimum value of K.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if the value of// mid gives at least (N/(M + 1))// candies or notbool check(int K, int n, int m, vector<int> arr, int good_share){ int candies = n, taken = 0; while (candies > 0) { // Candies taken by 1st // person is minimum of K // and candies left taken += min(K, candies); candies -= min(K, candies); // Traverse the given array for (int j = 0; j < m; j++) { // Amount consumed by // person j int consume = (arr[j] * candies) / 100; // Update the count of // candies candies -= consume; } } // Check if person 1 gets the // good share of candies return (taken >= good_share);}// Function to find minimum value of// K such that the first person gets// at least (N/(M+1)) candiesvoid minimumK(vector<int> &arr, int N, int M){ // Find the minimum required value // of candies for the first person int good_share = ceil((N * 1.0) / ((M + 1) * 1.0)); int lo = 1, hi = N; // Iterate until low is less // than or equal to mid while (lo < hi) { // Find the value of mid int mid = (lo + hi) / 2; // Check for mid, whether it // can be the possible value // of K or not if (check(mid, N, M, arr, good_share)) { // Update the value of hi hi = mid; } // Otherwise, update the // value of lo else { lo = mid + 1; } } // Print the resultant minimum // value of K cout << hi;}// Driver Codeint main(){ int N = 13, M = 1; vector<int> arr = { 50 }; minimumK(arr, N, M); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG {// Function to check if the value of// mid gives at least (N/(M + 1))// candies or notstatic boolean check(int K, int n, int m, ArrayList<Integer> arr, int good_share){ int candies = n, taken = 0; while (candies > 0) { // Candies taken by 1st // person is minimum of K // and candies left taken += Math.min(K, candies); candies -= Math.min(K, candies); // Traverse the given array for (int j = 0; j < m; j++) { // Amount consumed by // person j int consume = (arr.get(j) * candies) / 100; // Update the count of // candies candies -= consume; } } // Check if person 1 gets the // good share of candies return (taken >= good_share);}// Function to find minimum value of// K such that the first person gets// at least (N/(M+1)) candiesstatic void minimumK(ArrayList<Integer> arr, int N, int M){ // Find the minimum required value // of candies for the first person int good_share = (int)Math.ceil((N * 1.0) / ((M + 1) * 1.0)); int lo = 1, hi = N; // Iterate until low is less // than or equal to mid while (lo < hi) { // Find the value of mid int mid = (lo + hi) / 2; // Check for mid, whether it // can be the possible value // of K or not if (check(mid, N, M, arr, good_share)) { // Update the value of hi hi = mid; } // Otherwise, update the // value of lo else { lo = mid + 1; } } // Print the resultant minimum // value of K System.out.print(hi);}// Driver Codepublic static void main(String[] args){ int N = 13, M = 1; ArrayList<Integer> arr = new ArrayList<Integer>(); arr.add(50); minimumK(arr, N, M);}}// This code is contributed by avijitmondal1998. |
Python3
import mathclass GFG : # Function to check if the value of # mid gives at least (N/(M + 1)) # candies or not @staticmethod def check( K, n, m, arr, good_share) : candies = n taken = 0 while (candies > 0) : # Candies taken by 1st # person is minimum of K # and candies left taken += min(K,candies) candies -= min(K,candies) # Traverse the given array j = 0 while (j < m) : # Amount consumed by # person j consume = int((arr[j] * candies) / 100) # Update the count of # candies candies -= consume j += 1 # Check if person 1 gets the # good share of candies return (taken >= good_share) # Function to find minimum value of # K such that the first person gets # at least (N/(M+1)) candies @staticmethod def minimumK( arr, N, M) : # Find the minimum required value # of candies for the first person good_share = int(math.ceil((N * 1.0) / ((M + 1) * 1.0))) lo = 1 hi = N # Iterate until low is less # than or equal to mid while (lo < hi) : # Find the value of mid mid = int((lo + hi) / 2) # Check for mid, whether it # can be the possible value # of K or not if (GFG.check(mid, N, M, arr, good_share)) : # Update the value of hi hi = mid else : lo = mid + 1 # Print the resultant minimum # value of K print(hi, end ="") # Driver Code @staticmethod def main( args) : N = 13 M = 1 arr = [] arr.append(50) GFG.minimumK(arr, N, M) if __name__=="__main__": GFG.main([]) |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;class GFG { // Function to check if the value of // mid gives at least (N/(M + 1)) // candies or not static bool check(int K, int n, int m, List<int> arr, int good_share) { int candies = n, taken = 0; while (candies > 0) { // Candies taken by 1st // person is minimum of K // and candies left taken += Math.Min(K, candies); candies -= Math.Min(K, candies); // Traverse the given array for (int j = 0; j < m; j++) { // Amount consumed by // person j int consume = (arr[j] * candies) / 100; // Update the count of // candies candies -= consume; } } // Check if person 1 gets the // good share of candies return (taken >= good_share); } // Function to find minimum value of // K such that the first person gets // at least (N/(M+1)) candies static void minimumK(List<int> arr, int N, int M) { // Find the minimum required value // of candies for the first person int good_share = (int)Math.Ceiling( (N * 1.0) / ((M + 1) * 1.0)); int lo = 1, hi = N; // Iterate until low is less // than or equal to mid while (lo < hi) { // Find the value of mid int mid = (lo + hi) / 2; // Check for mid, whether it // can be the possible value // of K or not if (check(mid, N, M, arr, good_share)) { // Update the value of hi hi = mid; } // Otherwise, update the // value of lo else { lo = mid + 1; } } // Print the resultant minimum // value of K Console.WriteLine(hi); } // Driver Code public static void Main(string[] args) { int N = 13, M = 1; List<int> arr = new List<int>(); arr.Add(50); minimumK(arr, N, M); }}// This code is contributed by phasing17 |
Javascript
// Class in javascriptclass GFG { // Static method in javascript static check(K, n, m, arr, good_share) { let candies = n; let taken = 0; while (candies > 0) { // Candies taken by 1st person is minimum of K and candies left taken += Math.min(K, candies); candies -= Math.min(K, candies); // Traverse the given array let j = 0; while (j < m) { // Amount consumed by person j let consume = parseInt(((arr[j] * candies) / 100).toFixed(0)); // Update the count of candies candies -= consume; j += 1; } } // Check if person 1 gets the good share of candies return taken >= good_share; } // Function to find minimum value of K such that the first person gets at least (N/(M+1)) candies static minimumK(arr, N, M) { // Find the minimum required value of candies for the first person let good_share = Math.ceil((N * 1.0) / ((M + 1) * 1.0)); let lo = 1; let hi = N; // Iterate until low is less than or equal to mid while (lo < hi) { // Find the value of mid let mid = parseInt((lo + hi) / 2); // Check for mid, whether it can be the possible value of K or not if (GFG.check(mid, N, M, arr, good_share)) { // Update the value of hi hi = mid; } else { lo = mid + 1; } } // Print the resultant minimum value of K console.log(hi); } // Driver code in javascript static main(args) { let N = 13; let M = 1; let arr = []; arr.push(50); GFG.minimumK(arr, N, M); }}// Main function (function () { GFG.main([]);})();// This code is contributed by phasing17. |
Output
3
Time Complexity: O(N * log N)
Auxiliary Space: O(1)
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!
