Apply Operations to Maximize Score

Hard
1010.

Apply Operations to Maximize Score

Apply Operations to Maximize Score is a hard coding problem on arrays, math and sorting, asked in Amazon, Google and Microsoft interviews.

The prime score of an integer is its number of distinct prime factors — the prime score of 300 is 3, since 300 is 2² · 3 · 5².

Your score starts at 1. You may apply the following operation at most k times:

  • Pick a subarray nums[l..r] that you have not picked before.
  • Within it, choose the element with the highest prime score; on a tie, choose the one with the smallest index.
  • Multiply your score by that element.

Return the maximum score, modulo 10⁹ + 7.

Example 1

Input
nums = [8,3,9,3,8], k = 2
Output
81
Explanation
Every value has prime score 1, and `9` wins three different subarrays — so it can be taken twice.

Example 2

Input
nums = [19,12,14,6,10,18], k = 3
Output
4788
Explanation
`19` has prime score 1 so it wins only `[19]`; `18`, then `14`, are the next best. 19 · 18 · 14 = 4788.

Example 3

Input
nums = [2,3,5], k = 1
Output
5

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5
  • 1 <= k <= min(n * (n + 1) / 2, 10^9)
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maximumScore = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Apply Operations to Maximize Score — Problem & Solution

Apply Operations to Maximize Score solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Apply Operations to Maximize Score is a hard coding problem on arrays, math and sorting, asked in Amazon, Google and Microsoft interviews.

Problem statement

The prime score of an integer is its number of distinct prime factors — the prime score of 300 is 3, since 300 is 2² · 3 · 5².

Your score starts at 1. You may apply the following operation at most k times:

  • Pick a subarray nums[l..r] that you have not picked before.
  • Within it, choose the element with the highest prime score; on a tie, choose the one with the smallest index.
  • Multiply your score by that element.

Return the maximum score, modulo 10⁹ + 7.

Example 1

Input: nums = [8,3,9,3,8], k = 2
Output: 81
Explanation: Every value has prime score 1, and `9` wins three different subarrays — so it can be taken twice.

Example 2

Input: nums = [19,12,14,6,10,18], k = 3
Output: 4788
Explanation: `19` has prime score 1 so it wins only `[19]`; `18`, then `14`, are the next best. 19 · 18 · 14 = 4788.

Example 3

Input: nums = [2,3,5], k = 1
Output: 5

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5
  • 1 <= k <= min(n * (n + 1) / 2, 10^9)

Hints for Apply Operations to Maximize Score

  1. Hint 1

    First work out, for each index, how many subarrays would choose it. Then it is a pure greedy: spend k on the largest values first.

  2. Hint 2

    Index i wins a subarray [l, r] exactly when everything strictly left of it inside the window has a smaller prime score, and everything right has a score no greater.

  3. Hint 3

    That is two monotonic stacks: the previous index with score ≥, and the next index with score >. The product of the two gaps is the count.

How to solve Apply Operations to Maximize Score

Separate the two halves of the problem. First count, for each index, how many subarrays would select it — a classic "contribution of each element as the window maximum" computed with two monotonic stacks. Then the operations are unconstrained: sort the values descending and spend k on the largest, up to each one's count, accumulating the product with fast exponentiation.

Approach

  1. Sieve the distinct-prime-factor count up to max(nums): for each prime p, add one to every multiple of p.
  2. With a monotonic stack left to right, find left[i] — the nearest index before i whose score is ≥ s[i] (the tie-break sends ties left).
  3. With a stack right to left, find right[i] — the nearest index after i whose score is strictly > s[i].
  4. count[i] = (i - left[i]) * (right[i] - i).
  5. Sort indices by nums[i] descending; for each, take min(k, count[i]) copies via powmod, multiply into the answer and reduce k.
  6. Stop as soon as k reaches 0.

Why it works

The asymmetry between ≥ on the left and > on the right is exactly the leftmost-on-tie rule: an equal score to the left would beat i, so it blocks; an equal score to the right would lose, so it does not. Getting this backwards double-counts subarrays whenever two equal scores sit side by side. Once the counts are known the greedy is safe, because every operation is independent — nothing you take restricts what you can take next, so the largest available value is always the right choice.

Complexity

  • Time — O(n log n + M log log M) where M is max(nums)
  • Space — O(n + M)

Pitfalls

  • count[i] can reach about 5 · 10⁹, so it must be held in a 64-bit integer even though the answer fits an int after the modulo.
  • Multiplying two residues near 10⁹ overflows 53-bit floats — split the multiplication or use 64-bit integers.
  • Take the product modulo 10⁹ + 7 throughout; the running score is astronomically large otherwise.
  • Prime score counts distinct primes: 8 = 2³ scores 1, not 3.

Reference solution

Python

from typing import List

def maximumScore(nums: List[int], k: int) -> int:
    MOD = 10**9 + 7
    n = len(nums)
    maxv = max(nums)
    sieve = [0] * (maxv + 1)
    for p in range(2, maxv + 1):
        if sieve[p] == 0:
            for q in range(p, maxv + 1, p):
                sieve[q] += 1
    s = [sieve[v] for v in nums]
    left = [-1] * n
    right = [n] * n
    stack = []
    for i in range(n):
        while stack and s[stack[-1]] < s[i]:
            stack.pop()
        left[i] = stack[-1] if stack else -1
        stack.append(i)
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and s[stack[-1]] <= s[i]:
            stack.pop()
        right[i] = stack[-1] if stack else n
        stack.append(i)
    order = sorted(range(n), key=lambda i: -nums[i])
    ans = 1
    for i in order:
        if k == 0:
            break
        count = (i - left[i]) * (right[i] - i)
        take = min(count, k)
        ans = ans * pow(nums[i], take, MOD) % MOD
        k -= take
    return ans

Java

public static int maximumScore(int[] nums, int k) {
    final long MOD = 1000000007L;
    int n = nums.length;
    int maxv = 0;
    for (int v : nums) maxv = Math.max(maxv, v);
    int[] sieve = new int[maxv + 1];
    for (int p = 2; p <= maxv; p++) {
        if (sieve[p] == 0) {
            for (int q = p; q <= maxv; q += p) sieve[q]++;
        }
    }
    int[] s = new int[n];
    for (int i = 0; i < n; i++) s[i] = sieve[nums[i]];
    int[] left = new int[n];
    int[] right = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && s[stack.peek()] < s[i]) stack.pop();
        left[i] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(i);
    }
    stack.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (!stack.isEmpty() && s[stack.peek()] <= s[i]) stack.pop();
        right[i] = stack.isEmpty() ? n : stack.peek();
        stack.push(i);
    }
    Integer[] order = new Integer[n];
    for (int i = 0; i < n; i++) order[i] = i;
    Arrays.sort(order, (a, b) -> nums[b] - nums[a]);
    long remaining = k;
    long ans = 1;
    for (int t = 0; t < n && remaining > 0; t++) {
        int i = order[t];
        long count = (long) (i - left[i]) * (right[i] - i);
        long take = Math.min(count, remaining);
        long base = nums[i] % MOD;
        long e = take;
        long cur = 1;
        while (e > 0) {
            if ((e & 1L) == 1L) cur = cur * base % MOD;
            base = base * base % MOD;
            e >>= 1;
        }
        ans = ans * cur % MOD;
        remaining -= take;
    }
    return (int) ans;
}

C++

int maximumScore(vector<int>& nums, int k) {
    const long long MOD = 1000000007LL;
    int n = (int) nums.size();
    int maxv = 0;
    for (int v : nums) maxv = max(maxv, v);
    vector<int> sieve(maxv + 1, 0);
    for (int p = 2; p <= maxv; p++) {
        if (sieve[p] == 0) {
            for (int q = p; q <= maxv; q += p) sieve[q]++;
        }
    }
    vector<int> s(n), lft(n, -1), rgt(n, n);
    for (int i = 0; i < n; i++) s[i] = sieve[nums[i]];
    vector<int> stk;
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && s[stk.back()] < s[i]) stk.pop_back();
        lft[i] = stk.empty() ? -1 : stk.back();
        stk.push_back(i);
    }
    stk.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (!stk.empty() && s[stk.back()] <= s[i]) stk.pop_back();
        rgt[i] = stk.empty() ? n : stk.back();
        stk.push_back(i);
    }
    vector<int> order(n);
    for (int i = 0; i < n; i++) order[i] = i;
    sort(order.begin(), order.end(), [&](int a, int b) { return nums[a] > nums[b]; });
    long long remaining = k, ans = 1;
    for (int t = 0; t < n && remaining > 0; t++) {
        int i = order[t];
        long long count = (long long) (i - lft[i]) * (rgt[i] - i);
        long long take = min(count, remaining);
        long long base = nums[i] % MOD, e = take, cur = 1;
        while (e > 0) {
            if (e & 1LL) cur = cur * base % MOD;
            base = base * base % MOD;
            e >>= 1;
        }
        ans = ans * cur % MOD;
        remaining -= take;
    }
    return (int) ans;
}

JavaScript

var maximumScore = function(nums, k) {
    var MOD = 1000000007;
    var mulmod = function(a, b) {
        var ah = Math.floor(a / 65536), al = a % 65536;
        return ((ah * b % MOD) * 65536 + al * b) % MOD;
    };
    var powmod = function(base, exp) {
        var result = 1, bb = base % MOD, e = exp;
        while (e > 0) {
            if (e % 2 === 1) result = mulmod(result, bb);
            bb = mulmod(bb, bb);
            e = Math.floor(e / 2);
        }
        return result;
    };
    var n = nums.length, i, maxv = 0;
    for (i = 0; i < n; i++) if (nums[i] > maxv) maxv = nums[i];
    var sieve = [];
    for (i = 0; i <= maxv; i++) sieve.push(0);
    for (var p = 2; p <= maxv; p++) {
        if (sieve[p] === 0) for (var q = p; q <= maxv; q += p) sieve[q]++;
    }
    var s = [], left = [], right = [];
    for (i = 0; i < n; i++) { s.push(sieve[nums[i]]); left.push(-1); right.push(n); }
    var stack = [];
    for (i = 0; i < n; i++) {
        while (stack.length > 0 && s[stack[stack.length - 1]] < s[i]) stack.pop();
        left[i] = stack.length > 0 ? stack[stack.length - 1] : -1;
        stack.push(i);
    }
    stack = [];
    for (i = n - 1; i >= 0; i--) {
        while (stack.length > 0 && s[stack[stack.length - 1]] <= s[i]) stack.pop();
        right[i] = stack.length > 0 ? stack[stack.length - 1] : n;
        stack.push(i);
    }
    var order = [];
    for (i = 0; i < n; i++) order.push(i);
    order.sort(function(a, b) { return nums[b] - nums[a]; });
    var remaining = k, ans = 1;
    for (var t = 0; t < n && remaining > 0; t++) {
        var idx = order[t];
        var count = (idx - left[idx]) * (right[idx] - idx);
        var take = count < remaining ? count : remaining;
        ans = mulmod(ans, powmod(nums[idx], take));
        remaining -= take;
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms