Final Array State After K Multiplication Operations II solution and explanation

import heapq

MOD = 10**9 + 7
def finalArrayState(nums, k, multiplier):
    # Initialize min-heap
    h = [(val, i) for i, val in enumerate(nums)]
    heapq.heapify(h)

    while k > 0:
        # Pop minimum element
        min_val, min_idx = heapq.heappop(h)
        # Update and re-insert
        new_val = min_val * multiplier
        nums[min_idx] = new_val
        # Push back the new value
        heapq.heappush(h, (new_val, min_idx))
        k -= 1

    # Apply modulo operation
    return [num % MOD for num in nums]

#include <vector>
#include <queue>
#define MOD 1000000007
using namespace std;

vector<int> finalArrayState(vector<int>& nums, int k, int multiplier) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
    for (int i = 0; i < nums.size(); ++i) {
        minHeap.push({nums[i], i});
    }

    while (k-- > 0) {
        auto [minVal, index] = minHeap.top();
        minHeap.pop();
        nums[index] = minVal * multiplier;
        minHeap.push({nums[index], index});
    }

    for (int &num : nums) {
        num %= MOD;
    }
    return nums;
}

import java.util.*;

public class Solution {
    public static int[] finalArrayState(int[] nums, int k, int multiplier) {
        final int MOD = 1000000007;
        while (k-- > 0) {
            int minIdx = 0;
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] < nums[minIdx]) {
                    minIdx = i;
                }
            }
            nums[minIdx] *= multiplier;
        }

        for (int i = 0; i < nums.length; i++) {
            nums[i] %= MOD;
        }
        return nums;
    }
}

#include <stdlib.h>
#define MOD 1000000007

int* finalArrayState(int* nums, int numsSize, int k, int multiplier, int* returnSize){
    *returnSize = numsSize;
    
    while (k-- > 0) {
        int minIdx = 0;
        for (int i = 1; i < numsSize; i++) {
            if (nums[i] < nums[minIdx]) {
                minIdx = i;
            }
        }
        nums[minIdx] *= multiplier;
    }

    for (int i = 0; i < numsSize; i++) {
        nums[i] %= MOD;
    }

    return nums;
}

func getFinalState(nums []int, k int, multiplier int) []int {
	if multiplier == 1 {
		return nums
	}
	n := len(nums)
	pq := make(hp, n)
	for i, x := range nums {
		pq[i] = pair{x, i}
	}
	heap.Init(&pq)
	m := slices.Max(nums)
	for ; k > 0 && pq[0].x < m; k-- {
		x := pq[0]
		heap.Pop(&pq)
		x.x *= multiplier
		heap.Push(&pq, x)
	}
	const mod int = 1e9 + 7

	for i := range nums {
		p := heap.Pop(&pq).(pair)
		x, j := p.x, p.i
		power := k / n
		if i < k%n {
			power++
		}
		nums[j] = (x % mod) * qpow(multiplier, power, mod) % mod
	}
	return nums
}

func qpow(a, n, mod int) int {
	ans := 1 % mod
	a = a % mod
	for n > 0 {
		if n&1 == 1 {
			ans = (ans * a) % mod
		}
		a = (a * a) % mod
		n >>= 1
	}
	return int(ans)
}

type pair struct{ x, i int }
type hp []pair

func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].x < h[j].x || h[i].x == h[j].x && h[i].i < h[j].i }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(x any)        { *h = append(*h, x.(pair)) }
func (h *hp) Pop() (x any)      { a := *h; x = a[len(a)-1]; *h = a[:len(a)-1]; return x }