PowerfulDiscountTickets.java

class Item {
    long cost;
    int ticketsUsed;
    long discount;
    public Item(long cost, int ticketsUsed, long discount) {
        this.cost = cost;
        this.ticketsUsed = ticketsUsed;
        this.discount = discount;
    }
}
  
public void maximumDiscount(int N, int M) {
  
        long sum =0;
        // sort priority queue items in decreasing order of discount << important
        Queue<Item> queue = new PriorityQueue<Item>((it1,it2) -> (int)(it2.discount-it1.discount));
  
        for(int i=0;i<N;i++){
            long curr =  input.nextLong();
            sum += curr;
            Item item = new Item(curr, 1, curr-(curr/2));
            queue.offer(item);
        }

        for(int i=0;i<M;i++) {
            
            if(queue.isEmpty()) break;
            
            Item item = queue.poll();
            long oldCost = item.cost;
            long discount = item.discount;
            int ticketsUsed = item.ticketsUsed; 
            // substract discount from total each time we apply discount to an item
            sum -= discount;
            // since max price of item is 10^9, using 30 dicount tickets we can reduce the price to 0.
            if(ticketsUsed != 30) {              
                long newCost = oldCost;
                int newTicketsUsed = ticketsUsed+1;
                long newDiscount = oldCost/(1<<ticketsUsed) - oldCost/(1<<newTicketsUsed);

                Item newItem = new Item(newCost, newTicketsUsed, newDiscount);
                queue.offer(newItem);
            }
        }
        System.out.printf("%d\n", sum);  
    }