aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--min_balls_in_bag.c19
-rw-r--r--min_balls_in_bag.py35
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))