LeetCode

Editorial: LeetCode 1760 Minimum Limit of Balls in a Bag

Editorial: LeetCode 1760 Minimum Limit of Balls in a Bag

https://leetcode.com/problems/minimum-limit-of-balls-in-a-bag/ from Flipkart

Thinking process:

First observation is that given the maxOperations, we can create at most maxOperations new elements and thus the maximum number of balls in the bag should be (total number of balls)/(maxOperations + original size of the bag).

With that, we can calculate our goal first ((total number of balls)/(maxOperations + original size of the bag)), and then use a max heap to see who is bigger than our current goal, split them and put them back to the bag. Like the code below

 1class Solution {
 2public:
 3    int minimumSize(vector<int>& nums, int maxOperations) {
 4        int s = 0;
 5        for (auto n : nums) s += n;
 6        int goal = s/(nums.size() + maxOperations);
 7        if (goal == 0) goal++;
 8        priority_queue<int> pq;
 9        for (auto n : nums) pq.push(n);
10        for (int i=0; i<maxOperations; i++) {
11            int t = pq.top(); pq.pop();
12            pq.push(goal);
13            pq.push(t - goal);
14        }
15        return pq.top();
16    }
17};

This is not correct because sometimes there are some elements smaller than our goal and we don’t need to take them into account so that we can lower our goal.

Another way to do this is to guess our goal! That being said, we’ll guess a goal first, and everything above our goal should be split into smaller groups. We can then use binary search to find the minimum goal that has equal or less operations than maxOperations.

Here is the code.

 1class Solution {
 2public:
 3    int getOps(vector<int>& nums, int goal) {
 4        int ret = 0;
 5        for (auto n : nums) {
 6            ret += ((n-1)/goal);
 7        }
 8        return ret;
 9    }
10    int minimumSize(vector<int>& nums, int maxOperations) {
11        int M = *max_element(nums.begin(), nums.end());
12        int l = 1, r = M;
13        while (l < r) {
14            int mid = (l + r)/2;
15            if (getOps(nums, mid) > maxOperations) {
16                l = mid + 1;
17            } else {
18                r = mid;
19            }
20        }
21        return l;
22    }
23};
comments powered by Disqus