Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2558.html

2558. Take Gifts From the Richest Pile

Description

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.

 

Example 1:

Input: gifts = [25,64,9,4,100], k = 4
Output: 29
Explanation: 
The gifts are taken in the following way:
- In the first second, the last pile is chosen and 10 gifts are left behind.
- Then the second pile is chosen and 8 gifts are left behind.
- After that the first pile is chosen and 5 gifts are left behind.
- Finally, the last pile is chosen again and 3 gifts are left behind.
The final remaining gifts are [5,8,9,4,3], so the total number of gifts remaining is 29.

Example 2:

Input: gifts = [1,1,1,1], k = 4
Output: 4
Explanation: 
In this case, regardless which pile you choose, you have to leave behind 1 gift in each pile. 
That is, you can't take any pile with you. 
So, the total gifts remaining are 4.

 

Constraints:

• 1 <= gifts.length <= 103
• 1 <= gifts[i] <= 109
• 1 <= k <= 103

Solutions

• Java
• C++
• Python
• Go
• RenderScript
• TypeScript

• class Solution {
      public long pickGifts(int[] gifts, int k) {
          PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
          for (int v : gifts) {
              pq.offer(v);
          }
          while (k-- > 0) {
              pq.offer((int) Math.sqrt(pq.poll()));
          }
          long ans = 0;
          for (int v : pq) {
              ans += v;
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      long long pickGifts(vector<int>& gifts, int k) {
          make_heap(gifts.begin(), gifts.end());
          while (k--) {
              pop_heap(gifts.begin(), gifts.end());
              gifts.back() = sqrt(gifts.back());
              push_heap(gifts.begin(), gifts.end());
          }
          return accumulate(gifts.begin(), gifts.end(), 0LL);
      }
  };
  

• class Solution:
      def pickGifts(self, gifts: List[int], k: int) -> int:
          h = [-v for v in gifts]
          heapify(h)
          for _ in range(k):
              heapreplace(h, -int(sqrt(-h[0])))
          return -sum(h)
  
  

• func pickGifts(gifts []int, k int) (ans int64) {
  	h := &hp{gifts}
  	heap.Init(h)
  	for ; k > 0; k-- {
  		gifts[0] = int(math.Sqrt(float64(gifts[0])))
  		heap.Fix(h, 0)
  	}
  	for _, x := range gifts {
  		ans += int64(x)
  	}
  	return
  }
  
  type hp struct{ sort.IntSlice }
  
  func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
  func (hp) Pop() (_ interface{}) { return }
  func (hp) Push(interface{})     {}
  

• impl Solution {
      pub fn pick_gifts(gifts: Vec<i32>, k: i32) -> i64 {
          let mut h = std::collections::BinaryHeap::from(gifts);
          let mut ans = 0;
  
          for _ in 0..k {
              if let Some(mut max_gift) = h.pop() {
                  max_gift = (max_gift as f64).sqrt().floor() as i32;
                  h.push(max_gift);
              }
          }
  
          for x in h {
              ans += x as i64;
          }
  
          ans
      }
  }
  

• function pickGifts(gifts: number[], k: number): number {
      const pq = new MaxPriorityQueue();
      for (const v of gifts) {
          pq.enqueue(v, v);
      }
      while (k--) {
          let v = pq.dequeue().element;
          v = Math.floor(Math.sqrt(v));
          pq.enqueue(v, v);
      }
      let ans = 0;
      while (!pq.isEmpty()) {
          ans += pq.dequeue().element;
      }
      return ans;
  }
  
  

All Problems

All Solutions