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⁹ + 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.

https://leetcode.cn/problems/final-array-state-after-k-multiplication-operations-ii/

Example 1:

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]

Example 2:

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 <= 10⁴
  • 1 <= nums[i] <= 10⁹
  • 1 <= k <= 10⁹
  • 1 <= multiplier <= 10⁶

Test Cases

1
2
class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
solution_test.py
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
import pytest

from solution import Solution


@pytest.mark.parametrize('nums, k, multiplier, expected', [
    ([2,1,3,5,6], 5, 2, [8,4,6,5,6]),
    ([100000,2000], 2, 1000000, [999999307,999999993]),

    ([1,2], 3, 4, [16,8]),

    ([2,5,1,5,1,1,3,5], 5, 2, [4,5,4,5,2,2,3,5]),
    ([1,1,1000000000], 3, 1000000, [999993007,1000000,1000000000]),
    ([66307295,441787703,589039035,322281864], 900900704, 641725, [664480092, 763599523, 886046925, 47878852]),
    ([889458628,338743558,875422936,684907163,233489834], 246181588, 313380, [940635593,321154185,859014034,48349682,391180073]),
    (
        [3,9,27,81,243,729,2187,6561,19683,59049,177147,531441,1594323,4782969,14348907,43046721,129140163,387420489],
        1000000000, 3,
        [869770420,623256809,623256809,623256809,623256809,623256809,623256809,623256809,623256809,623256809,623256809,623256809,623256809,623256809,623256809,623256809,623256809,623256809]
    ),
    (
        [2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912],
        1000000000, 2,
        [112329828,112329828,112329828,112329828,112329828,112329828,112329828,112329828,112329828,112329828,112329828,112329828,112329828,112329828,112329828,112329828,112329828,112329828,56164914,56164914,56164914,56164914,56164914,56164914,56164914,56164914,56164914,56164914,56164914]
    ),
    (
        [5,25,125,625,3125,15625,78125,390625,1953125,9765625,48828125,244140625],
        1000000000, 5,
        [676863159,676863159,676863159,676863159,676863159,676863159,676863159,676863159,676863159,676863159,735372636,735372636]
    ),
])
class Test:
    def test_solution(self, nums, k, multiplier, expected):
        sol = Solution()
        assert sol.getFinalState(nums.copy(), k, multiplier) == expected

Thoughts

这可能是提交遇到解答错误次数最多的一题了。

3264. Final Array State After K Multiplication Operations I 的进阶版。不只是 n = nums.length 从 100 提升到 10⁴，k 也从 10 提升到了 10⁹。

Huge “k”

先看变得更大的 k，从 1 遍历到 k 肯定是跑不动的。但这个跟 1760. Minimum Limit of Balls in a Bag 非常像（指最大堆的那种实现方式，而非二分法），巨大的 k 其实会给每个数字都平摊很多，可以先计算出每个数字平摊多少，直接乘上去，可以省掉大量的循环。

设 nums 中的最大值为 top。先把所有其他数字通过乘以 multiplier 的某个次方，增大到不超过 top，即修改之后的数组满足：对于任意的 i，nums[i] <= top < nums[i] * multiplier。设某个数字是 v，那么 p = ⌊log(top / v, multiplier)⌋，让 v 乘以 multiplier 的 p 次方即可。

这里有个坑，在 Python 里直接计算 log(a, b) 结果可能会有些偏差，导致下取整会少 1。比如 log(3**17, 3) = 16.999999999999996，比如 log10(5**7) / log10(5) = 6.999999999999999。即使用 decimal 也同样会遇到 bad case。目前的处理方法是计算完之后根据情况修正一下：

1
2
3
4
5
6
def ilog(a: int, b: int) -> int:
    """Calculates int(log(a, b))."""
    p = int(log10(a) / log10(b))
    if b ** (p + 1) <= a:
        p += 1
    return p

可以发现这个状态下，每连续 n 次操作就刚好给 nums 中每个数字都乘以 multiplier 一次。设前边为了达到这个状态需要 t 次操作，那么 (k - t) // n 就是每个数字平摊到的操作次数。不妨设 divmod(k - t, n) = q, r。

先看剩下的零头 r（0 ≤ r < n）。只需要对目前 nums 中最小的 r 个数字，分别乘以 multiplier 一次即可。可以用大小为 r 的最大堆找出最小的 r 个数字，时间为 n log r = O(n log n)。

需要注意取模之后再比较大小就没意义了，所以在确定好最小的 r 个数字之前，不要取模。因为 nums 中所有值都不超过 top，也就不需要取模。

然后给 nums 中每个数字都乘以 multiplier 的 q 次方。注意到这里的 q 依然非常大，需要使用二分法进行幂运算，时间复杂度可以降到 O(log q) = O(log k - log n) ≈ O(log k)。

二分法幂运算在 935. Knight Dialer 和 70. Climbing Stairs 都有涉及（矩阵的幂运算跟整数的幂运算没有本质区别）。在这两题中计算幂用的是正向的循环，如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
MOD = 1_000_000_007

def bi_power(a: int, n: int) -> int:
    """Calculates x ** n % MOD."""
    if n == 0: return 1
    mask = 1
    n1 = n
    while n1 := n1 >> 1:
        mask <<= 1
    res = a
    while mask := mask >> 1:
        res = res * res % MOD
        if n & mask:
            res = res * a % MOD
    return res

还有另外一种计算方式，本题用的是这种方式：

1
2
3
4
5
6
7
8
9
10
11
12
MOD = 1_000_000_007

def bi_power(a: int, n: int) -> int:
    """Calculates x ** n % MOD."""
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % MOD
        n >>= 1
        a = a * a % MOD

    return res

至此就计算完成了，把当前的 nums 返回即可。时间复杂度 O((n log n) + (log k))，空间复杂度 O(n)。

Normal “k”

上边的处理的基础是 k 足够大，足够把 nums 所有数字都增大到刚好不超过 top。但如果 k 没有那么大，就还是按照 3264. Final Array State After K Multiplication Operations I 中那样，用最小堆来处理。

时间复杂度 O((n + k) log n)，空间复杂度 O(n)。

一个小的优化是类似 1760. Minimum Limit of Balls in a Bag 里的处理，取当前最小值 a，看第二小的值 b，直接对 a 操作若干次使它刚好超过 b。令 p = ⌈log(b + 1 - a, multiplier)⌉，如果剩余的次数足够，那就给 a 加上 multiplier 的 p 次方，再放回堆中。

注意需要保证对于相同的两个数，要优先对在 nums 中排在前边的数字操作。所以如果 b 的下标小于 a 的下标，就令 p = ⌈log(b - a), multiplier⌉，确保 a 不会超过 b。

另外考虑到 Python 的 log 浮点误差问题，虽然没有实际遇到 log 结果上取整有错，但保险起见还是可以特殊处理一下：

1
2
3
4
5
6
def clog(a: int, b: int) -> int:
    """Calculates ceil(log(a, b))."""
    p = ceil(log10(a) / log10(b))
    if b ** (p - 1) > a:
        p -= 1
    return p

另外注意取模之后再排序就无效了，所以运算过程中不能取模。但进入这个处理逻辑的前提是 k 不够把 nums 所有数字都增大到刚好不超过 top，也就不用取模。

Code

solution.py
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
from heapq import heapify, heappop, heappush, heappushpop
from math import ceil, log10

MOD = 1_000_000_007


# def bi_power(a: int, n: int) -> int:
#     """Calculates x ** n % MOD."""
#     if n == 0: return 1
#     mask = 1
#     n1 = n
#     while n1 := n1 >> 1:
#         mask <<= 1

#     res = a
#     while mask := mask >> 1:
#         res = res * res % MOD
#         if n & mask:
#             res = res * a % MOD

#     return res


def bi_power(a: int, n: int) -> int:
    """Calculates x ** n % MOD."""
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % MOD
        n >>= 1
        a = a * a % MOD

    return res


def ilog(a: int, b: int) -> int:
    """Calculates int(log(a, b))."""
    p = int(log10(a) / log10(b))
    if b ** (p + 1) <= a:
        p += 1
    return p


def clog(a: int, b: int) -> int:
    """Calculates ceil(log(a, b))."""
    p = ceil(log10(a) / log10(b))
    if b ** (p - 1) > a:
        p -= 1
    return p


class Solution:
    def getFinalState(self, nums: list[int], k: int, multiplier: int) -> list[int]:
        if multiplier == 1: return nums

        n = len(nums)
        top = max(nums)
        powers: dict[int, int] = {} # i: ilog(top / nums[i], multiplier)
        t = 0
        for i in range(n):
            p = ilog(top / nums[i], multiplier)
            if p == 0: continue
            t += p
            if t > k: break
            powers[i] = p
        else:
            share, k = divmod(k - t, n)
            for i, p in powers.items():
                nums[i] *= multiplier ** p

            if k > 0:
                heap = [(-nums[i], -i) for i in range(k)] # A max-heap to get the minimal k values.
                heapify(heap)
                for i in range(k, n):
                    heappushpop(heap, (-nums[i], -i))
                for _, i in heap:
                    nums[-i] = nums[-i] * multiplier % MOD

            if share > 0:
                tmp = bi_power(multiplier, share)
                for i in range(n):
                    nums[i] = nums[i] * tmp % MOD

            return nums

        heap = [(v, i) for i, v in enumerate(nums)]
        heapify(heap)
        while k > 0:
            a, i = heappop(heap)
            b, j = heap[0]
            if j > i: b += 1

            p = clog(b / a, multiplier)
            if p > k:
                p = k

            a *= multiplier ** p
            k -= p
            heappush(heap, (a, i))

        result = [0] * n
        for v, i in heap:
            result[i] = v % MOD
        return result
hard
参考资料
许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章

快来参与讨论吧~