diff options
-rw-r--r-- | min_balls_in_bag.c | 19 | ||||
-rw-r--r-- | min_balls_in_bag.py | 35 |
2 files changed, 43 insertions, 11 deletions
diff --git a/min_balls_in_bag.c b/min_balls_in_bag.c index c95c0ef..b2f7a3f 100644 --- a/min_balls_in_bag.c +++ b/min_balls_in_bag.c @@ -1,6 +1,5 @@ // 1760. Minimum Limit of Balls in a Bag -#include <stdbool.h> -#include <stdio.h> +#include "leetcode.h" /* * given an integer array 'nums' where the i'th bag contains @@ -12,19 +11,17 @@ * after the operations. return the minimum possible penalty. */ -bool work(int *nums, int nums_size, int operation, int min) { - for (int i = 0; i < nums_size && operation >= 0; i++) +bool work(int *nums, int numsSize, int operation, int min) { + for (int i = 0; i < numsSize && operation >= 0; i++) operation -= (nums[i] - 1) / min; return operation >= 0; } -int minimumSize(int *nums, int nums_size, int max_operations) { - int i = 1, j = 1000000000, k; - bool can; +int minimumSize(int *nums, int numsSize, int max_operations) { + int i = 1, j = INT_MAX, k; while (i < j) { k = (i + j) / 2; - can = work(nums, nums_size, max_operations, k); - if (can) + if (work(nums, numsSize, max_operations, k)) j = k; else i = k + 1; @@ -34,6 +31,6 @@ int minimumSize(int *nums, int nums_size, int max_operations) { int main() { int n1[] = {9}, n2[] = {2, 4, 8, 2}; - printf("%d\n", minimumSize(n1, 1, 2)); // expect: 3 - printf("%d\n", minimumSize(n2, 4, 4)); // expect: 2 + printf("%d\n", minimumSize(n1, ARRAY_SIZE(n1), 2)); // expect: 3 + printf("%d\n", minimumSize(n2, ARRAY_SIZE(n2), 4)); // expect: 2 } diff --git a/min_balls_in_bag.py b/min_balls_in_bag.py new file mode 100644 index 0000000..07b7ce5 --- /dev/null +++ b/min_balls_in_bag.py @@ -0,0 +1,35 @@ +# 1760. Minimum Limit of Balls in a Bag +from bisect import bisect_left + +""" +given an integer array 'nums' where the i'th bag contains +'nums[i]' balls. also given an integer 'max_operations'. +you can perform the following operation at most 'max_operations' +times; take any bag of balls and divide it into two new bags +with a positive number of balls. the penalty is the maximum +number of balls in a bag. you want to minimise your penalty +after the operations. return the minimum possible penalty. +""" + + +class Solution(object): + def minimumSize(self, nums, maxOperations): + """ + :type nums: List[int] + :type maxOperations: int + :rtype: int + """ + return ( + bisect_left( + range(1, max(nums) + 1), + 0, + key=lambda x: maxOperations - sum((k - 1) // x for k in nums), + ) + + 1 + ) + + +if __name__ == "__main__": + obj = Solution() + print(obj.minimumSize(nums=[9], maxOperations=2)) + print(obj.minimumSize(nums=[2, 4, 8, 2], maxOperations=4)) |