aboutsummaryrefslogtreecommitdiff
path: root/apply_operations_max_score.py
blob: d0834dedea6d0c6d1acd0339745506a143208804 (plain)
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
# 2818. Apply Operations to Maximize Score

"""
you are given an array 'nums' of 'n' positive integers and an integer 'k'.
initially, you start with a score of 1. you have to maxmise your score by
applying the following operation at most 'k' times: chose any non-empty
element 'x' of 'nums[l .. r]' with the highest prime score. if multiple such
elements exist, choose the one with the smallest index. multiple your score
'x'. return the maximum possible score after applying at most 'k' operations.
since the answer may be very large, return it module '10e9+7'
"""


class Solution(object):
    mod = 10**9 + 7

    def mod_pow(self, x, n):
        res = 1
        while n > 0:
            if n % 2 == 1:
                res = (res * x) % self.mod
            x = (x * x) % self.mod
            n //= 2
        return res

    def maximumScore(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        n = len(nums)
        upper = max(nums) + 1
        prime = [True] * upper
        prime[0] = prime[1] = False
        score = [0] * upper
        for i in range(2, upper):
            if prime[i]:
                for j in range(i, upper, i):
                    score[j] += 1
                    prime[j] = False
        next, stk = [n] * n, []
        for i in range(n - 1, -1, -1):
            while stk and score[nums[i]] >= score[nums[stk[-1]]]:
                stk.pop()
            next[i] = stk[-1] if stk else n
            stk.append(i)
        prev, stk = [-1] * n, []
        for i in range(n):
            while stk and score[nums[i]] > score[nums[stk[-1]]]:
                stk.pop()
            prev[i] = stk[-1] if stk else -1
            stk.append(i)
        ans = 1
        tuples = [[nums[i], i] for i in range(n)]
        tuples.sort(reverse=True)
        for num, idx in tuples:
            operations = min(
                (idx - prev[idx]) * (next[idx] - idx),
                k,
            )
            ans = (ans * self.mod_pow(num, operations)) % self.mod
            k -= operations
            if k == 0:
                return ans
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.maximumScore(nums=[8, 3, 9, 3, 8], k=2))
    print(obj.maximumScore(nums=[19, 12, 14, 6, 10, 18], k=3))