Given an integer, P denoting the number of chocolates and an array a[] where ai denotes the type of ith chocolate. There are N people who want to eat chocolate every day. Find the maximum number of consecutive days for which N people can eat chocolates considering the following conditions:
- Each of the N people must eat exactly one chocolate on a particular day.
- A single person can eat chocolate of the same type only for all days.
Examples:
Input: N = 4, P = 10, arr[] = {1, 5, 2, 1, 1, 1, 2, 5, 7, 2}
Output: 2
Explanation: Chocolates can be assigned in the following way:
Person 1: Type 1
Person 2: Type 1
Person 3: Type 2
Person 4: Type 5
In this way, there are sufficient chocolates for each person to eat one chocolate for two consecutive days. No other possible distribution of chocolates can make the people eat the chocolates for more than 2 days.Input: N = 3, P = 10, arr[] = {1, 2, 2, 1, 1, 3, 3, 3, 2, 4}
Output: 3
Explanation: Chocolates can be distributed in the following way:
Person 1: Type 1
Person 2: Type 2
Person 3: Type 3
In this way, all the 3 people can eat their respective assigned type of chocolates for three days.
Approach: Follow the steps below to solve the problem:
- The minimum number of days for which it is possible to distribute the chocolates is 0 and the maximum number is P.
- So, for each number X in this range, check if it is possible to distribute chocolates to each person for X days.
- For all such Xs, find the maximum.
- Now, using Binary Search check for all the numbers in the range 0 to P.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Stores the frequency of// each type of chocolatemap<int, int> mp;int N, P;// Function to check if chocolates// can be eaten for 'mid' no. of daysbool helper(int mid){ int cnt = 0; for (auto i : mp) { int temp = i.second; while (temp >= mid) { temp -= mid; cnt++; } } // If cnt exceeds N, // return true return cnt >= N;}// Function to find the maximum// number of days for which// chocolates can be eatenint findMaximumDays(int arr[]){ // Store the frequency // of each type of chocolate for (int i = 0; i < P; i++) { mp[arr[i]]++; } // Initialize start and end // with 0 and P respectively int start = 0, end = P, ans = 0; while (start <= end) { // Calculate mid int mid = start + ((end - start) / 2); // Check if chocolates can be // distributed for mid days if (mid != 0 and helper(mid)) { ans = mid; // Check if chocolates can // be distributed for more // than mid consecutive days start = mid + 1; } else if (mid == 0) { start = mid + 1; } else { end = mid - 1; } } return ans;}// Driver codeint main(){ N = 3, P = 10; int arr[] = { 1, 2, 2, 1, 1, 3, 3, 3, 2, 4 }; // Function call cout << findMaximumDays(arr); return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{// Stores the frequency of// each type of chocolatestatic HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); static int N, P;// Function to check if chocolates// can be eaten for 'mid' no. of daysstatic boolean helper(int mid){ int cnt = 0; for(Map.Entry<Integer, Integer> i : mp.entrySet()) { int temp = i.getValue(); while (temp >= mid) { temp -= mid; cnt++; } } // If cnt exceeds N, // return true return cnt >= N;}// Function to find the maximum// number of days for which// chocolates can be eatenstatic int findMaximumDays(int arr[]){ // Store the frequency // of each type of chocolate for(int i = 0; i < P; i++) { if (mp.containsKey(arr[i])) { mp.put(arr[i], mp.get(arr[i]) + 1); } else { mp.put(arr[i], 1); } } // Initialize start and end // with 0 and P respectively int start = 0, end = P, ans = 0; while (start <= end) { // Calculate mid int mid = start + ((end - start) / 2); // Check if chocolates can be // distributed for mid days if (mid != 0 && helper(mid)) { ans = mid; // Check if chocolates can // be distributed for more // than mid consecutive days start = mid + 1; } else if (mid == 0) { start = mid + 1; } else { end = mid - 1; } } return ans;}// Driver codepublic static void main(String[] args){ N = 3; P = 10; int arr[] = { 1, 2, 2, 1, 1, 3, 3, 3, 2, 4 }; // Function call System.out.print(findMaximumDays(arr));}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program to implement# the above approach# Stores the frequency of# each type of chocolatemp = {}N, P = 0, 0# Function to check if chocolates# can be eaten for 'mid' no. of daysdef helper(mid): cnt = 0; for i in mp: temp = mp[i] while (temp >= mid): temp -= mid cnt += 1 # If cnt exceeds N, # return true return cnt >= N# Function to find the maximum# number of days for which# chocolates can be eatendef findMaximumDays(arr): # Store the frequency # of each type of chocolate for i in range(P): mp[arr[i]] = mp.get(arr[i], 0) + 1 # Initialize start and end # with 0 and P respectively start = 0 end = P ans = 0 while (start <= end): # Calculate mid mid = start + ((end - start) // 2) # Check if chocolates can be # distributed for mid days if (mid != 0 and helper(mid)): ans = mid # Check if chocolates can # be distributed for more # than mid consecutive days start = mid + 1 elif (mid == 0): start = mid + 1 else: end = mid - 1 return ans# Driver codeif __name__ == '__main__': N = 3 P = 10 arr = [ 1, 2, 2, 1, 1, 3, 3, 3, 2, 4 ] # Function call print(findMaximumDays(arr))# This code is contributed by mohit kumar 29 |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG{// Stores the frequency of// each type of chocolatestatic Dictionary<int, int> mp = new Dictionary<int, int>(); static int N, P;// Function to check if // chocolates can be eaten // for 'mid' no. of daysstatic bool helper(int mid){ int cnt = 0; foreach(KeyValuePair<int, int> i in mp) { int temp = i.Value; while (temp >= mid) { temp -= mid; cnt++; } } // If cnt exceeds N, // return true return cnt >= N;}// Function to find the maximum// number of days for which// chocolates can be eatenstatic int findMaximumDays(int []arr){ // Store the frequency // of each type of chocolate for(int i = 0; i < P; i++) { if (mp.ContainsKey(arr[i])) { mp[arr[i]] = mp[arr[i]] + 1; } else { mp.Add(arr[i], 1); } } // Initialize start and end // with 0 and P respectively int start = 0, end = P, ans = 0; while (start <= end) { // Calculate mid int mid = start + ((end - start) / 2); // Check if chocolates can be // distributed for mid days if (mid != 0 && helper(mid)) { ans = mid; // Check if chocolates can // be distributed for more // than mid consecutive days start = mid + 1; } else if (mid == 0) { start = mid + 1; } else { end = mid - 1; } } return ans;}// Driver codepublic static void Main(String[] args){ N = 3; P = 10; int []arr = {1, 2, 2, 1, 1, 3, 3, 3, 2, 4}; // Function call Console.Write(findMaximumDays(arr));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program to implement// the above approach// Stores the frequency of// each type of chocolatevar mp = new Map();var N, P;// Function to check if chocolates// can be eaten for 'mid' no. of daysfunction helper(mid){ var cnt = 0; mp.forEach((value,) => { var temp = value; while (temp >= mid) { temp -= mid; cnt++; } }); // If cnt exceeds N, // return true return cnt >= N;}// Function to find the maximum// number of days for which// chocolates can be eatenfunction findMaximumDays(arr){ // Store the frequency // of each type of chocolate for (var i = 0; i < P; i++) { if(mp.has(arr[i])) mp.set(arr[i], mp.get(arr[i])+1) else mp.set(arr[i], 1); } // Initialize start and end // with 0 and P respectively var start = 0, end = P, ans = 0; while (start <= end) { // Calculate mid var mid = start + parseInt((end - start) / 2); // Check if chocolates can be // distributed for mid days if (mid != 0 && helper(mid)) { ans = mid; // Check if chocolates can // be distributed for more // than mid consecutive days start = mid + 1; } else if (mid == 0) { start = mid + 1; } else { end = mid - 1; } } return ans;}// Driver codeN = 3, P = 10;var arr = [1, 2, 2, 1, 1, 3, 3, 3, 2, 4 ];// Function calldocument.write( findMaximumDays(arr));</script> |
Output
3
Time Complexity: O(N * log N)
Auxiliary Space: O(N)
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!
