aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-11-13 22:07:00 -0700
committerJack Sangdahl <[email protected]>2024-11-13 22:07:08 -0700
commitecc2fcf61ab52d10b402d8d87146c06c53c4c423 (patch)
tree7db88fd93e87bd70be7e4a1718581f0c818796f3
parent6ce80ea59406da5284927cffc5cf770fb1f09bcd (diff)
downloadleetcode-ecc2fcf61ab52d10b402d8d87146c06c53c4c423.tar.gz
leetcode-ecc2fcf61ab52d10b402d8d87146c06c53c4c423.zip
2064. minimised maximum of products distributed to any store
-rw-r--r--mini_maxi_products_distrib.c45
-rw-r--r--mini_maxi_products_distrib.py38
2 files changed, 83 insertions, 0 deletions
diff --git a/mini_maxi_products_distrib.c b/mini_maxi_products_distrib.c
new file mode 100644
index 0000000..7ea4016
--- /dev/null
+++ b/mini_maxi_products_distrib.c
@@ -0,0 +1,45 @@
+// 2064. Minimized Maximum of Products Distributed to Any Store
+#include "leetcode.h"
+
+/*
+ * you are given an integer 'n' indicating that there are 'n' specialty retail
+ * stores. there are 'm' product types of varying amounts, which are given as a
+ * 0-indexed integer array 'quantities' owhere 'quantities[i]' represents the
+ * number of products of the i'th product type. you need to distribute all the
+ * products to the retail stores following these rules: a store can only be
+ * given at most one product type but can be given any amount of it, and after
+ * distribution, each store will have been given some number products. let 'x'
+ * represent the maximum number of products given to any store. you want 'x' to
+ * be as small as possible. return the minimum possible 'x'.
+ */
+
+int minimizedMaximum(int n, int *quantities, int quantitiesSize) {
+ long long sum = 0;
+ int right = 0;
+ for (int i = 0; i < quantitiesSize; ++i) {
+ sum += quantities[i];
+ if (right < quantities[i])
+ right = quantities[i];
+ }
+ if (sum < n)
+ return 1;
+ int left = (int)(sum / n), mid = 0, groups = 0;
+ while (left <= right) {
+ mid = left + (right - left) / 2;
+ groups = 0;
+ for (int i = 0; i < quantitiesSize; i++)
+ groups += (quantities[i] + mid - 1) / mid;
+ if (groups <= n)
+ right = mid - 1;
+ else
+ left = mid + 1;
+ }
+ return left;
+}
+
+int main() {
+ int q1[] = {11, 6}, q2[] = {15, 10, 10}, q3[] = {100000};
+ printf("%d\n", minimizedMaximum(6, q1, ARRAY_SIZE(q1))); // expect: 3
+ printf("%d\n", minimizedMaximum(7, q2, ARRAY_SIZE(q2))); // expect: 5
+ printf("%d\n", minimizedMaximum(1, q3, ARRAY_SIZE(q3))); // expect: 100000
+}
diff --git a/mini_maxi_products_distrib.py b/mini_maxi_products_distrib.py
new file mode 100644
index 0000000..3baae0a
--- /dev/null
+++ b/mini_maxi_products_distrib.py
@@ -0,0 +1,38 @@
+# 2064. Minimized Maximum of Products Distributed to Any Store
+from math import ceil
+
+"""
+you are given an integer 'n' indicating that there are 'n' specialty retail
+stores. there are 'm' product types of varying amounts, which are given as a
+0-indexed integer array 'quantities' owhere 'quantities[i]' represents the
+number of products of the i'th product type. you need to distribute all the
+products to the retail stores following these rules: a store can only be
+given at most one product type but can be given any amount of it, and after
+distribution, each store will have been given some number products. let 'x'
+represent the maximum number of products given to any store. you want 'x' to
+be as small as possible. return the minimum possible 'x'.
+"""
+
+
+class Solution(object):
+ def minimizedMaximum(self, n, quantities):
+ """
+ :type n: int
+ :type quantities: List[int]
+ :rtype: int
+ """
+ right, left = 0, max(quantities)
+ while right + 1 < left:
+ mid = (right + left) // 2
+ if sum(ceil(i / mid) for i in quantities) <= n:
+ left = mid
+ else:
+ right = mid
+ return left
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minimizedMaximum(n=6, quantities=[11, 6]))
+ print(obj.minimizedMaximum(n=7, quantities=[15, 10, 10]))
+ print(obj.minimizedMaximum(n=1, quantities=[100000]))