Maximum Product After K Increments

class Solution {
public:
    int maximumProduct(vector<int>& nums, int k) {
        const int MOD = 1'000'000'007;
        priority_queue<int, vector<int>, greater<int>> pq(nums.begin(), nums.end());
        while (k--) {
            int x = pq.top(); pq.pop();
            pq.push(x + 1);
        }
        long long prod = 1;
        while (!pq.empty()) {
            prod = (prod * pq.top()) % MOD;
            pq.pop();
        }
        return (int)prod;
    }
};

import "container/heap"

type minHeap []int

func (h minHeap) Len() int            { return len(h) }
func (h minHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h minHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *minHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func maximumProduct(nums []int, k int) int {
    const MOD = 1_000_000_007
    pq := &minHeap{}
    for _, x := range nums {
        *pq = append(*pq, x)
    }
    heap.Init(pq)
    for ; k > 0; k-- {
        x := heap.Pop(pq).(int)
        heap.Push(pq, x+1)
    }
    prod := int64(1)
    for pq.Len() > 0 {
        prod = (prod * int64(heap.Pop(pq).(int))) % MOD
    }
    return int(prod)
}

import heapq
from typing import List

class Solution:
    def maximumProduct(self, nums: List[int], k: int) -> int:
        MOD = 10**9 + 7
        heap = nums[:]
        heapq.heapify(heap)
        for _ in range(k):
            x = heapq.heappop(heap)
            heapq.heappush(heap, x + 1)
        prod = 1
        for x in heap:
            prod = (prod * x) % MOD
        return prod

class MinHeap {
    constructor(arr = []) {
        this.h = arr.slice();
        for (let i = (this.h.length >> 1) - 1; i >= 0; i--) this._down(i);
    }
    size() { return this.h.length; }
    push(v) {
        this.h.push(v);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p] <= this.h[i]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop() {
        const top = this.h[0];
        const last = this.h.pop();
        if (this.h.length > 0) {
            this.h[0] = last;
            this._down(0);
        }
        return top;
    }
    _down(i) {
        const n = this.h.length;
        while (true) {
            const l = 2 * i + 1, r = 2 * i + 2;
            let s = i;
            if (l < n && this.h[l] < this.h[s]) s = l;
            if (r < n && this.h[r] < this.h[s]) s = r;
            if (s === i) break;
            [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
            i = s;
        }
    }
}

function maximumProduct(nums, k) {
    const MOD = 1000000007n;
    const pq = new MinHeap(nums);
    for (let i = 0; i < k; i++) {
        const x = pq.pop();
        pq.push(x + 1);
    }
    let prod = 1n;
    while (pq.size() > 0) {
        prod = (prod * BigInt(pq.pop())) % MOD;
    }
    return Number(prod);
}

class Solution {
    public int maximumProduct(int[] nums, int k) {
        final int MOD = 1_000_000_007;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int x : nums) pq.offer(x);
        while (k-- > 0) {
            int x = pq.poll();
            pq.offer(x + 1);
        }
        long prod = 1;
        while (!pq.isEmpty()) {
            prod = (prod * pq.poll()) % MOD;
        }
        return (int) prod;
    }
}

class MinHeap {
    private h: number[];
    constructor(arr: number[] = []) {
        this.h = arr.slice();
        for (let i = (this.h.length >> 1) - 1; i >= 0; i--) this.down(i);
    }
    size(): number { return this.h.length; }
    push(v: number): void {
        this.h.push(v);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p] <= this.h[i]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop(): number {
        const top = this.h[0];
        const last = this.h.pop() as number;
        if (this.h.length > 0) {
            this.h[0] = last;
            this.down(0);
        }
        return top;
    }
    private down(i: number): void {
        const n = this.h.length;
        while (true) {
            const l = 2 * i + 1, r = 2 * i + 2;
            let s = i;
            if (l < n && this.h[l] < this.h[s]) s = l;
            if (r < n && this.h[r] < this.h[s]) s = r;
            if (s === i) break;
            [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
            i = s;
        }
    }
}

function maximumProduct(nums: number[], k: number): number {
    const MOD = 1000000007n;
    const pq = new MinHeap(nums);
    for (let i = 0; i < k; i++) {
        const x = pq.pop();
        pq.push(x + 1);
    }
    let prod = 1n;
    while (pq.size() > 0) {
        prod = (prod * BigInt(pq.pop())) % MOD;
    }
    return Number(prod);
}