diff options
author | Jack Sangdahl <[email protected]> | 2024-12-11 20:58:22 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-11 20:58:22 -0700 |
commit | 3da02bd52f9772af30f9336da114b7f37e8a5025 (patch) | |
tree | c5b499ddbc788164eb1de26283aedc289c09971f | |
parent | 20cefbfd4f00a9404bbf1e026f14a4dc3cc9ac16 (diff) | |
download | leetcode-3da02bd52f9772af30f9336da114b7f37e8a5025.tar.gz leetcode-3da02bd52f9772af30f9336da114b7f37e8a5025.zip |
2558. take gifts from the richest pile
-rw-r--r-- | take_gifts_richest_pile.c | 33 | ||||
-rw-r--r-- | take_gifts_richest_pile.py | 35 |
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)) |