1962. Remove Stones to Minimize the Total

You are given a 0-indexed integer array piles, where piles[i] represents the number of stones in the ith 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 smaller 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 2. The resulting piles are [4,3,3,7].
- Apply the operation on pile 3. 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 <= 105
1 <= piles[i] <= 104
1 <= k <= 105

//approach -1 (use sorting )Brute force method
//time complexity : O(k*nlogn)
//space complexity : O(1)
gives TLE
public static int minStoneSum(int[] piles, int k) {
        while(k-->0){
            Arrays.sort(piles);
            piles[piles.length-1]-=(int)(piles[piles.length-1]/2);
        }
        int ans=0;
        for(int i=0;i< piles.length;i++){
            ans+=piles[i];
        }
        //System.out.println(ans);
        return ans;
    }
    //approach -2 (find max element every time brute force)
    //t.c : O(k*n)
    //space com. : O(1)
    
    //approach - 3(using min or max heap / priority queue)(optimised)
    
    //t.c : O(n + k*logn)
    //space com. : O(n)
    class Solution {
    public static int minStoneSum(int[] piles, int k) {
        //PriorityQueue<Integer> cur=new PriorityQueue<>(Comparator.reverseOrder());
        PriorityQueue<Integer> temp=new PriorityQueue<>(Collections.reverseOrder());
        for(int i=0;i< piles.length;i++){
            //cur.add(piles[i]);
            temp.add(piles[i]);
        }
//        while(cur.size()>0){
//            System.out.print(cur.poll());
//        }
        //System.out.println();
        while(k-->0){
            int cur=temp.poll();
            temp.add(cur-(cur/2));
        }
        long ans=0;
        while (temp.size()>0){
            ans+=temp.poll();
        }
        return (int)ans;
    }
}