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
- Precompute the smallest prime factor up to
max(nums)to get each element's prime score quickly. - 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.
- That count is the number of operations for which the index is available, and each index can be used at most
counttimes. - Greedily assign the largest
numsvalues to the indices with the largest counts, using fast modular exponentiation sincekcan 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]taketimes in a loop:kreaches 10^9, so modular exponentiation withpowis 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.