Problem

You are given an integer array nums, an integer k, and an integer multiplier.

You need to perform k operations on nums. In each operation:

  • Find the minimum value x in nums. If there are multiple occurrences of the minimum value, select the one that appears first.
  • Replace the selected minimum value x with x * multiplier.

After the k operations, apply modulo 10^9 + 7 to every value in nums.

Return an integer array denoting the final state of nums after performing all k operations and then applying the modulo.

Examples

Example 1:

1
2
3

Input: nums = [2,1,3,5,6], k = 5, multiplier = 2
Output: [8,4,6,5,6]
Explanation:
Operation Result
After operation 1 [2, 2̲, 3, 5, 6]
After operation 2 [4̲, 2, 3, 5, 6]
After operation 3 [4, 4̲, 3, 5, 6]
After operation 4 [4, 4, 6̲, 5, 6]
After operation 5 [8̲, 4, 6, 5, 6]
After applying modulo [8, 4, 6, 5, 6]

Example 2:

1
2
3

Input: nums = [100000,2000], k = 2, multiplier = 1000000
Output: [999999307,999999993]
Explanation:
Operation Result
After operation 1 [100000, 2000000000]
After operation 2 [100000000000, 2000000000]
After applying modulo [999999307, 999999993]

Constraints:

  • 1 <= nums.length <= 104
  • 1 <= nums[i] <= 109
  • 1 <= k <= 109
  • 1 <= multiplier <= 106

Solution

Method 1 – Greedy Distribution with Exponentiation by Squaring

Intuition

The key idea is to distribute the multiplication operations as evenly as possible among all indices. We first ensure that every element receives at least one operation, so that no element remains the smallest after the first round. After this, we distribute the remaining operations as evenly as possible, using the fact that multiplying by the multiplier repeatedly grows the value exponentially. To efficiently compute large powers, we use exponentiation by squaring.

Approach

  1. If the multiplier is 1, return the array as is (since multiplying by 1 has no effect).
  2. Use a min-heap (priority queue) to always select the smallest element and apply the operation, ensuring each element gets at least one operation.
  3. After all elements have received at least one operation (or k runs out), record the current state.
  4. Distribute the remaining operations as evenly as possible: each index gets k // n more, and the first k % n indices get one extra.
  5. For each index, compute the final value using fast exponentiation (exponentiation by squaring) to handle large powers efficiently.
  6. Apply modulo 10^9 + 7 to each value and return the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution {
public:
    const long long mod = 1e9 + 7;
    long long power_mod(long long base, long long exp, long long mod) {
        long long res = 1;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % mod;
            base = (base * base) % mod;
            exp /= 2;
        }
        return res;
    }
    vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
        if (multiplier == 1) return nums;
        int n = nums.size();
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
        for (int i = 0; i < n; i++) pq.push({nums[i], i});
        unordered_set<int> done;
        while ((int)done.size() < n && k > 0) {
            auto [val, idx] = pq.top(); pq.pop();
            val *= multiplier;
            pq.push({val, idx});
            done.insert(idx);
            k--;
        }
        vector<long long> v(n);
        while (!pq.empty()) {
            auto [val, idx] = pq.top(); pq.pop();
            v[idx] = val;
        }
        int rep = k / n, md = k % n;
        vector<int> ops(n, rep);
        for (int i = 0; i < n; i++) if (md-- > 0) ops[i]++;
        for (int i = 0; i < n; i++) {
            long long mlt = power_mod(multiplier, ops[i], mod);
            v[i] = (v[i] % mod) * (mlt % mod) % mod;
            nums[i] = v[i];
        }
        return nums;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

func powerMod(base, exp, mod int64) int64 {
    res := int64(1)
    for exp > 0 {
        if exp%2 == 1 {
            res = (res * base) % mod
        }
        base = (base * base) % mod
        exp /= 2
    }
    return res
}
func getFinalState(nums []int, k int, multiplier int) []int {
    if multiplier == 1 {
        return nums
    }
    n := len(nums)
    type pair struct{ val, idx int64 }
    h := &minHeap{}
    for i, v := range nums {
        heap.Push(h, pair{int64(v), int64(i)})
    }
    done := map[int64]bool{}
    for len(done) < n && k > 0 {
        p := heap.Pop(h).(pair)
        p.val *= int64(multiplier)
        heap.Push(h, p)
        done[p.idx] = true
        k--
    }
    v := make([]int64, n)
    for h.Len() > 0 {
        p := heap.Pop(h).(pair)
        v[p.idx] = p.val
    }
    rep, md := k/n, k%n
    ops := make([]int, n)
    for i := range ops {
        ops[i] = rep
        if i < md {
            ops[i]++
        }
    }
    modv := int64(1e9 + 7)
    for i := 0; i < n; i++ {
        mlt := powerMod(int64(multiplier), int64(ops[i]), modv)
        v[i] = (v[i]%modv)*(mlt%modv)%modv
        nums[i] = int(v[i])
    }
    return nums
}
// minHeap implementation omitted for brevity
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class Solution {
    static final long MOD = 1_000_000_007;
    long powerMod(long base, long exp, long mod) {
        long res = 1;
        while (exp > 0) {
            if ((exp & 1) == 1) res = (res * base) % mod;
            base = (base * base) % mod;
            exp >>= 1;
        }
        return res;
    }
    public int[] getFinalState(int[] nums, int k, int multiplier) {
        if (multiplier == 1) return nums;
        int n = nums.length;
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        for (int i = 0; i < n; i++) pq.offer(new long[]{nums[i], i});
        Set<Long> done = new HashSet<>();
        while (done.size() < n && k > 0) {
            long[] p = pq.poll();
            p[0] *= multiplier;
            pq.offer(p);
            done.add(p[1]);
            k--;
        }
        long[] v = new long[n];
        while (!pq.isEmpty()) {
            long[] p = pq.poll();
            v[(int)p[1]] = p[0];
        }
        int rep = k / n, md = k % n;
        int[] ops = new int[n];
        for (int i = 0; i < n; i++) {
            ops[i] = rep;
            if (i < md) ops[i]++;
        }
        for (int i = 0; i < n; i++) {
            long mlt = powerMod(multiplier, ops[i], MOD);
            v[i] = (v[i] % MOD) * (mlt % MOD) % MOD;
            nums[i] = (int)v[i];
        }
        return nums;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class Solution {
    private val MOD = 1_000_000_007L
    private fun powerMod(base: Long, exp: Long, mod: Long): Long {
        var res = 1L
        var b = base
        var e = exp
        while (e > 0) {
            if (e % 2 == 1L) res = (res * b) % mod
            b = (b * b) % mod
            e /= 2
        }
        return res
    }
    fun getFinalState(nums: IntArray, k: Int, multiplier: Int): IntArray {
        if (multiplier == 1) return nums
        val n = nums.size
        val pq = java.util.PriorityQueue<Pair<Long, Int>>(compareBy { it.first })
        for (i in 0 until n) pq.add(nums[i].toLong() to i)
        val done = mutableSetOf<Int>()
        var kk = k
        while (done.size < n && kk > 0) {
            val (v, idx) = pq.poll()
            pq.add((v * multiplier) to idx)
            done.add(idx)
            kk--
        }
        val v = LongArray(n)
        while (pq.isNotEmpty()) {
            val (valx, idx) = pq.poll()
            v[idx] = valx
        }
        val rep = kk / n
        var md = kk % n
        val ops = IntArray(n) { rep }
        for (i in 0 until n) if (i < md) ops[i]++
        for (i in 0 until n) {
            val mlt = powerMod(multiplier.toLong(), ops[i].toLong(), MOD)
            v[i] = (v[i] % MOD) * (mlt % MOD) % MOD
            nums[i] = v[i].toInt()
        }
        return nums
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

import heapq
class Solution:
    def powerMod(self, base: int, exp: int, mod: int) -> int:
        res = 1
        while exp > 0:
            if exp % 2 == 1:
                res = (res * base) % mod
            base = (base * base) % mod
            exp //= 2
        return res
    def getFinalState(self, nums: list[int], k: int, multiplier: int) -> list[int]:
        if multiplier == 1:
            return nums
        n = len(nums)
        h = [(v, i) for i, v in enumerate(nums)]
        heapq.heapify(h)
        done = set()
        while len(done) < n and k > 0:
            v, idx = heapq.heappop(h)
            v *= multiplier
            heapq.heappush(h, (v, idx))
            done.add(idx)
            k -= 1
        v = [0] * n
        while h:
            val, idx = heapq.heappop(h)
            v[idx] = val
        rep, md = divmod(k, n)
        ops = [rep] * n
        for i in range(md):
            ops[i] += 1
        modv = 10 ** 9 + 7
        for i in range(n):
            mlt = self.power_mod(multiplier, ops[i], modv)
            v[i] = (v[i] % modv) * (mlt % modv) % modv
            nums[i] = v[i]
        return nums
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

impl Solution {
    pub fn get_final_state(nums: Vec<i32>, mut k: i32, multiplier: i32) -> Vec<i32> {
        use std::collections::{BinaryHeap, HashSet};
        use std::cmp::Reverse;
        let n = nums.len();
        if multiplier == 1 { return nums; }
        let mut h = nums.into_iter().enumerate().map(|(i, v)| (v as i64, i)).collect::<Vec<_>>();
        h.sort();
        let mut done = HashSet::new();
        while done.len() < n && k > 0 {
            let (v, idx) = h.remove(0);
            h.push((v * multiplier as i64, idx));
            h.sort();
            done.insert(idx);
            k -= 1;
        }
        let mut v = vec![0i64; n];
        for (val, idx) in h { v[idx] = val; }
        let rep = k / n as i32;
        let md = k % n as i32;
        let mut ops = vec![rep; n];
        for i in 0..md as usize { ops[i] += 1; }
        let modv = 1_000_000_007i64;
        fn power_mod(mut base: i64, mut exp: i32, modv: i64) -> i64 {
            let mut res = 1i64;
            while exp > 0 {
                if exp % 2 == 1 { res = res * base % modv; }
                base = base * base % modv;
                exp /= 2;
            }
            res
        }
        let mut res = vec![0i32; n];
        for i in 0..n {
            let mlt = power_mod(multiplier as i64, ops[i], modv);
            v[i] = (v[i] % modv) * (mlt % modv) % modv;
            res[i] = v[i] as i32;
        }
        res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
    powerMod(base: number, exp: number, mod: number): number {
        let res = 1;
        while (exp > 0) {
            if (exp % 2 === 1) res = (res * base) % mod;
            base = (base * base) % mod;
            exp = Math.floor(exp / 2);
        }
        return res;
    }
    getFinalState(nums: number[], k: number, multiplier: number): number[] {
        if (multiplier === 1) return nums;
        const n = nums.length;
        const h: [number, number][] = nums.map((v, i) => [v, i]);
        h.sort((a, b) => a[0] - b[0]);
        const done = new Set<number>();
        while (done.size < n && k > 0) {
            const [v, idx] = h.shift()!;
            h.push([v * multiplier, idx]);
            h.sort((a, b) => a[0] - b[0]);
            done.add(idx);
            k--;
        }
        const v = Array(n).fill(0);
        for (const [val, idx] of h) v[idx] = val;
        const rep = Math.floor(k / n), md = k % n;
        const ops = Array(n).fill(rep);
        for (let i = 0; i < md; i++) ops[i]++;
        const modv = 1_000_000_007;
        for (let i = 0; i < n; i++) {
            const mlt = this.powerMod(multiplier, ops[i], modv);
            v[i] = (v[i] % modv) * (mlt % modv) % modv;
            nums[i] = v[i];
        }
        return nums;
    }
}

Complexity

  • ⏰ Time complexity: O(n log k), since each operation is distributed efficiently and exponentiation is logarithmic.
  • 🧺 Space complexity: O(n), for the heap and auxiliary arrays.