aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--take_gifts_richest_pile.c33
-rw-r--r--take_gifts_richest_pile.py35
2 files changed, 68 insertions, 0 deletions
diff --git a/take_gifts_richest_pile.c b/take_gifts_richest_pile.c
new file mode 100644
index 0000000..3d53cb9
--- /dev/null
+++ b/take_gifts_richest_pile.c
@@ -0,0 +1,33 @@
+// 2558. Take Gifts From the Richest Pile
+#include "leetcode.h"
+
+/*
+ * you are given an integer array 'gifts' denoting the number of gifts in
+ * various piles. every second, you do the following: choose the pile with the
+ * maximum number of gifts, if there is more than one pile with the maximum
+ * number of gifts, choose any. leave behind the floor of the square root of the
+ * number of gifts in the pile. take the rest of the gifts. return the number of
+ * gifts remaining after 'k' seconds.
+ */
+
+long long pickGifts(int *gifts, int giftsSize, int k) {
+ long long ans = 0;
+ for (int i = 0; i < k; i++) {
+ int max = 0, x;
+ for (int j = 0; j < giftsSize; j++)
+ if (max < gifts[j]) {
+ max = gifts[j];
+ x = j;
+ }
+ gifts[x] = sqrt(gifts[x]);
+ }
+ for (int i = 0; i < giftsSize; i++)
+ ans += gifts[i];
+ return ans;
+}
+
+int main() {
+ int g1[] = {25, 64, 9, 4, 100}, g2[] = {1, 1, 1, 1};
+ printf("%lld\n", pickGifts(g1, ARRAY_SIZE(g1), 4)); // expect: 29
+ printf("%lld\n", pickGifts(g2, ARRAY_SIZE(g2), 4)); // expect: 4
+}
diff --git a/take_gifts_richest_pile.py b/take_gifts_richest_pile.py
new file mode 100644
index 0000000..caa9616
--- /dev/null
+++ b/take_gifts_richest_pile.py
@@ -0,0 +1,35 @@
+# 2558. Take Gifts From the Richest Pile
+import heapq
+from math import isqrt
+
+"""
+you are given an integer array 'gifts' denoting the number of gifts in
+various piles. every second, you do the following: choose the pile with the
+maximum number of gifts, if there is more than one pile with the maximum
+number of gifts, choose any. leave behind the floor of the square root of the
+number of gifts in the pile. take the rest of the gifts. return the number of
+gifts remaining after 'k' seconds.
+"""
+
+
+class Solution(object):
+ def pickGifts(self, gifts, k):
+ """
+ :type gifts: List[int]
+ :type k: int
+ :rtype: int
+ """
+ gifts = [-i for i in gifts]
+ heapq.heapify(gifts)
+ x, i = 1 << 32, 0
+ while i < k and x > 1:
+ x = -heapq.heappop(gifts)
+ heapq.heappush(gifts, -isqrt(x))
+ i += 1
+ return -sum(gifts)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.pickGifts(gifts=[25, 64, 9, 4, 100], k=4))
+ print(obj.pickGifts(gifts=[1, 1, 1, 1], k=4))