Welcome to Subscribe On Youtube

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

1962. Remove Stones to Minimize the Total

Level

Medium

Description

You are given a 0-indexed integer array piles, where piles[i] represents the number of stones in the i-th pile, and an integer k. You should apply the following operation exactly k times:

  • Choose any piles[i] and remove floor(piles[i] / 2) stones from it.

Notice that you can apply the operation on the same pile more than once.

Return the minimum possible total number of stones remaining after applying the k operations.

floor(x) is the greatest integer that is smaller8* than or **equal to x (i.e., rounds x down).

Example 1:

Input: piles = [5,4,9], k = 2

Output: 12

Explanation: Steps of a possible scenario are:

  • Apply the operation on pile 2. The resulting piles are [5,4,5].
  • Apply the operation on pile 0. The resulting piles are [3,4,5].

The total number of stones in [3,4,5] is 12.

Example 2:

Input: piles = [4,3,6,7], k = 3

Output: 12

Explanation: Steps of a possible scenario are:

  • Apply the operation on pile 3. The resulting piles are [4,3,3,7].
  • Apply the operation on pile 4. The resulting piles are [4,3,3,4].
  • Apply the operation on pile 0. The resulting piles are [2,3,3,4].

The total number of stones in [2,3,3,4] is 12.

Constraints:

  • 1 <= piles.length <= 10^5
  • 1 <= piles[i] <= 10^4
  • 1 <= k <= 10^5

Solution

Use a greedy approach. To make the total number of stones remaining minimum, each time remove the most stones as possible. Therefore, each time select the pile with the maximum number of stones, and remove half of the stones from the pile. Use a priority queue to maintain the piles for each operation. Finally, return the sum of the remaining stones.

  • class Solution {
    public int minStoneSum(int[] piles, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>((a, b) -> (b - a));
        for (int pile : piles)
            priorityQueue.offer(pile);
        for (int i = 0; i < k; i++) {
            int pile = priorityQueue.poll();
            pile = pile - pile / 2;
            priorityQueue.offer(pile);
        }
        int sum = 0;
        while (!priorityQueue.isEmpty())
            sum += priorityQueue.poll();
        return sum;
    }
}

############

class Solution {
    public int minStoneSum(int[] piles, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> (b - a));
        for (int p : piles) {
            q.offer(p);
        }
        while (k-- > 0) {
            int p = q.poll();
            q.offer((p + 1) >> 1);
        }
        int ans = 0;
        while (!q.isEmpty()) {
            ans += q.poll();
        }
        return ans;
    }
}

  • // OJ: https://leetcode.com/problems/remove-stones-to-minimize-the-total/
// Time: O((N + K) * logN)
// Space: O(N)
class Solution {
public:
    int minStoneSum(vector<int>& A, int k) {
        priority_queue<int> pq;
        for (int n : A) pq.push(n);
        long rm = 0, sum = accumulate(begin(A), end(A), 0L);
        for (int i = 0; i < k; ++i) {
            int n = pq.top();
            pq.pop();
            if (n == 1) break;
            rm += n / 2;
            pq.push(n - n / 2);
        }
        return sum - rm;
    }
};

  • class Solution:
    def minStoneSum(self, piles: List[int], k: int) -> int:
        h = []
        for p in piles:
            heappush(h, -p)
        for _ in range(k):
            p = -heappop(h)
            heappush(h, -((p + 1) >> 1))
        return -sum(h)

############

# 1962. Remove Stones to Minimize the Total
# https://leetcode.com/problems/remove-stones-to-minimize-the-total/

class Solution:
    def minStoneSum(self, piles: List[int], k: int) -> int:
        heap = [-pile for pile in piles]
        heapq.heapify(heap)

        for _ in range(k):
            pile = -heapq.heappop(heap)
            heapq.heappush(heap, -ceil(pile / 2))
            
        return sum([-pile for pile in heap])


  • func minStoneSum(piles []int, k int) int {
    q := &hp{piles}
    heap.Init(q)
    for k > 0 {
        p := q.pop()
        q.push((p + 1) >> 1)
        k--
    }
    ans := 0
    for q.Len() > 0 {
        ans += q.pop()
    }
    return ans
}

type hp struct{ sort.IntSlice }

func (h hp) Less(i, j int) bool  { return h.IntSlice[i] > h.IntSlice[j] }
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() interface{} {
	a := h.IntSlice
	v := a[len(a)-1]
	h.IntSlice = a[:len(a)-1]
	return v
}
func (h *hp) push(v int) { heap.Push(h, v) }
func (h *hp) pop() int   { return heap.Pop(h).(int) }

  • function minStoneSum(piles: number[], k: number): number {
    const pq = new MaxPriorityQueue();
    for (const x of piles) {
        pq.enqueue(x);
    }
    while (k--) {
        const x = pq.dequeue().element;
        pq.enqueue(x - ((x / 2) | 0));
    }
    let ans = 0;
    while (pq.size()) {
        ans += pq.dequeue().element;
    }
    return ans;
}

All Problems

All Solutions