⚡Flashcard Drill➔
NeetCode #828LC-2818HardGreedy
← Back to All Problems

#828 · #2818 · Apply Operations to Maximize Score(操作使得分最大)

📌 Problem Statement & Constraints

You are given an array nums and an integer k. The prime score of a number is its count of distinct prime factors. In one operation, pick an index i you have not used, multiply your score (initially 1) by nums[i], and mark i used. Choose indices to maximise the score after exactly k operations, and return it modulo 10^9 + 7. When several indices tie on prime score, the smaller index wins. Constraints: 1 <= nums.length <= 10^4, 1 <= nums[i] <= 10^5, 1 <= k <= 10^9.

💡 Core Algorithmic Approaches

  1. Precompute the smallest prime factor up to max(nums) to get each element's prime score quickly.
  2. An index is selectable for a subarray if it holds the maximum prime score in it, with ties going to the leftmost index; monotonic stacks count how many subarrays choose each index.
  3. That count is the number of operations for which the index is available, and each index can be used at most count times.
  4. Greedily assign the largest nums values to the indices with the largest counts, using fast modular exponentiation since k can reach 10^9.

💻 Benchmark Python3 Implementation

class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        MOD = 10 ** 9 + 7
        n = len(nums)
        mx = max(nums)
        spf = list(range(mx + 1))               # smallest prime factor sieve
        i = 2
        while i * i <= mx:
            if spf[i] == i:
                for j in range(i * i, mx + 1, i):
                    if spf[j] == j:
                        spf[j] = i
            i += 1

        def prime_score(x: int) -> int:
            cnt = 0
            while x > 1:
                p = spf[x]
                cnt += 1
                while x % p == 0:
                    x //= p
            return cnt

        score = [prime_score(v) for v in nums]

        # previous index with prime score >= current (leftmost-maximum tie-break)
        prev_ge = [-1] * n
        stack = []
        for i in range(n):
            while stack and score[stack[-1]] < score[i]:
                stack.pop()
            prev_ge[i] = stack[-1] if stack else -1
            stack.append(i)

        # next index with prime score strictly greater than current
        next_g = [n] * n
        stack = []
        for i in range(n - 1, -1, -1):
            while stack and score[stack[-1]] <= score[i]:
                stack.pop()
            next_g[i] = stack[-1] if stack else n
            stack.append(i)

        # number of subarrays in which index i is the chosen (leftmost maximal) index
        contrib = [(next_g[i] - i) * (i - prev_ge[i]) for i in range(n)]

        order = sorted(range(n), key=lambda i: -nums[i])
        ans = 1
        for i in order:
            if k <= 0:
                break
            take = min(k, contrib[i])
            ans = ans * pow(nums[i], take, MOD) % MOD
            k -= take
        return ans

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(M log log M + n log n + n log k): the sieve, the sort, and modular exponentiation.
💾 Space Complexity
O(M + n): the sieve array and the auxiliary stacks.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the tie-break rule: on equal prime scores the leftmost index is chosen, which forces the asymmetric stack conditions (< on one side, <= on the other).
  • Using the prime score of 1 as 0: 1 has no prime factors, so its score is 0, which is correct and matters for the tie-break boundaries.
  • Multiplying nums[i] take times in a loop: k reaches 10^9, so modular exponentiation with pow is required.
  • Sorting by index instead of value: the greedy must consume the largest values first, paired with the largest availability counts.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems