aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-09-14 15:36:23 -0600
committerJack Sangdahl <[email protected]>2024-09-14 15:36:23 -0600
commit541bfbfc4625b97f3c6eb9978621ba3311beeed5 (patch)
tree394207fe28d7584d9546450e46b474ede5e5248d
parent7d6ce37fbb409bc5c6675eeabb58166abe463aef (diff)
downloadleetcode-541bfbfc4625b97f3c6eb9978621ba3311beeed5.tar.gz
leetcode-541bfbfc4625b97f3c6eb9978621ba3311beeed5.zip
1648. sell diminishing valued coloured balls
Signed-off-by: Jack Sangdahl <[email protected]>
-rw-r--r--sell_diminishing_value_colour_balls.c54
-rw-r--r--sell_diminishing_value_colour_balls.py43
2 files changed, 97 insertions, 0 deletions
diff --git a/sell_diminishing_value_colour_balls.c b/sell_diminishing_value_colour_balls.c
new file mode 100644
index 0000000..eb2e116
--- /dev/null
+++ b/sell_diminishing_value_colour_balls.c
@@ -0,0 +1,54 @@
+// 1648. Sell Diminishing-Valued Colored Balls
+#include "leetcode.h"
+
+/*
+ * you have an 'inventory' of different coloured balls, and there is a customer
+ * that wants 'orders' balls of any colour. the customer weirdly midues the
+ * coloured balls. each coloured ball's midue is the number of balls of that
+ * colours you currently have in your 'inventory'. for example, if you own 6
+ * yellow balls, the customer would pay 6 for the first yellow ball. after the
+ * transaction, there are only 5 yellow balls left, so the next yellow ball is
+ * then midued at 5. you are given an integer array 'inventory' where
+ * 'inventory[i]' represents the number of balls of the i'th colour that you
+ * initially own. you are also given an integer 'orders' which represents the
+ * total number of balls that the customer wants. you can sell the balls in any
+ * order.
+ */
+
+int maxProfit(int *inventory, int inventorySize, int orders) {
+ int right = 0, left = 0, mid;
+ long num, profit;
+ const int mod = 1e9 + 7;
+ for (int i = 0; i < inventorySize; i++)
+ if (inventory[i] > right)
+ right = inventory[i];
+ while (left <= right) {
+ num = 0;
+ mid = (left + right) / 2;
+ for (int i = 0; i < inventorySize; i++)
+ if (inventory[i] > mid)
+ num += inventory[i] - mid;
+ if (num == orders)
+ break;
+ else if (num < orders)
+ right = mid - 1;
+ else
+ left = mid + 1;
+ }
+ for (int i = 0; i < inventorySize; i++)
+ if (inventory[i] > mid)
+ profit += (long)(inventory[i] + mid + 1) * (long)(inventory[i] - mid) / 2;
+ if (num > orders)
+ profit = (profit - (num - orders) * (mid + 1)) % mod;
+ else if (num < orders)
+ profit = (profit + (orders - num) * mid) % mod;
+ else
+ profit %= mod;
+ return (int)profit;
+}
+
+int main() {
+ int i1[] = {2, 5}, i2[] = {3, 5};
+ printf("%d\n", maxProfit(i1, ARRAY_SIZE(i1), 4)); // expect: 14
+ printf("%d\n", maxProfit(i2, ARRAY_SIZE(i2), 6)); // expect: 19
+}
diff --git a/sell_diminishing_value_colour_balls.py b/sell_diminishing_value_colour_balls.py
new file mode 100644
index 0000000..d37abf1
--- /dev/null
+++ b/sell_diminishing_value_colour_balls.py
@@ -0,0 +1,43 @@
+# 1648. Sell Diminishing-Valued Colored Balls
+from collections import Counter
+
+"""
+you have an 'inventory' of different coloured balls, and there is a customer
+that wants 'orders' balls of any colour. the customer weirdly midues the
+coloured balls. each coloured ball's midue is the number of balls of that
+colours you currently have in your 'inventory'. for example, if you own 6
+yellow balls, the customer would pay 6 for the first yellow ball. after the
+transaction, there are only 5 yellow balls left, so the next yellow ball is
+then midued at 5. you are given an integer array 'inventory' where
+'inventory[i]' represents the number of balls of the i'th colour that you
+initially own. you are also given an integer 'orders' which represents the
+total number of balls that the customer wants. you can sell the balls in any
+order.
+"""
+
+
+class Solution(object):
+ def maxProfit(self, inventory, orders):
+ """
+ :type inventory: List[int]
+ :type orders: int
+ :rtype: int
+ """
+ arr = sorted(Counter(inventory).items(), reverse=True) + [(0, 0)]
+ ans, idx, width = 0, 0, 0
+ while orders > 0:
+ width += arr[idx][1]
+ sell = min(orders, width * (arr[idx][0] - arr[idx + 1][0]))
+ whole, rem = divmod(sell, width)
+ ans += width * (
+ whole * (arr[idx][0] + arr[idx][0] - (whole - 1))
+ ) // 2 + rem * (arr[idx][0] - whole)
+ orders -= sell
+ idx += 1
+ return ans % (10**9 + 7)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maxProfit(inventory=[2, 5], orders=4))
+ print(obj.maxProfit(inventory=[3, 5], orders=6))