Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Apply Operations to Maximize Score solution and explanation

HardArrayGreedyMathMonotonic Stack7 min read53.7% acceptanceUpdated 9 Apr 2026
Asked atGoogleMeta
Practise Apply Operations to Maximize Score
34:45
Apply Operations to Maximize Score - Leetcode 2818 - PythonNeetCodeIO · 34:45 · 10K viewsWatch on YouTube
9 more videos on this problem
  1. Apply Operations to Maximize Score - Leetcode 2818 - PythonNeetCodeIO · 34:45 · 10K views
  2. Apply Operations to Maximize Score | Super Detailed Approach For Beginners | Leetcode 2818 | MIKcodestorywithMIK · 1:20:52 · 8K views
  3. Apply Operations to Maximize Score | Leetcode 2818Techdose · 28:03 · 4K views
  4. 2818. Apply Operations to Maximize Score | Weekly Leetcode 358codingMohan · 34:59 · 1K views
  5. Leetcode Weekly contest 358 - Hard- Apply Operations to Maximize ScorePrakhar Agrawal · 19:16 · 1K views
  6. 2818. Apply Operations to Maximize Score | LeetCode Weekly Contest 358Binary Brains · 14:34 · 625 views
  7. 2818 Apply Operations to Maximize Score | LeetCodeR Sai Siddhu · 25:49 · 616 views
  8. 2818. Apply Operations to Maximize Score (Leetcode Hard)Programming Live with Larry · 1:12:37 · 477 views
  9. 2818. Apply Operations to Maximize Score | Leetcode Daily - PythonLeetcode Daily · 9:19 · 144 views
  10. 2818. Apply Operations to Maximize Score | Leetcode Hardquebeat · 42:18 · 122 views

The problem

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 maximize your score by applying the following operation at most k times:

  • Choose any non-empty subarray nums[l, ..., r] that you haven't chosen previously.
  • Choose an element x of nums[l, ..., r] with the highest prime score. If multiple such elements exist, choose the one with the smallest index.
  • Multiply your score by x.

Here, nums[l, ..., r] denotes the subarray of nums starting at index l and ending at the index r, both ends being inclusive.

The prime score of an integer x is equal to the number of distinct prime factors of x. For example, the prime score of 300 is 3 since 300 = 2 * 2 * 3 * 5 * 5.

Return the maximum possible score after applying at most k operations.

Since the answer may be large, return it modulo 109 + 7.

Example 1:

Input: nums = [8,3,9,3,8], k = 2
Output: 81
Explanation: To get a score of 81, we can apply the following operations:
- Choose subarray nums[2, ..., 2]. nums[2] is the only element in this subarray. Hence, we multiply the score by nums[2]. The score becomes 1 * 9 = 9.
- Choose subarray nums[2, ..., 3]. Both nums[2] and nums[3] have a prime score of 1, but nums[2] has the smaller index. Hence, we multiply the score by nums[2]. The score becomes 9 * 9 = 81.
It can be proven that 81 is the highest score one can obtain.

Example 2:

Input: nums = [19,12,14,6,10,18], k = 3
Output: 4788
Explanation: To get a score of 4788, we can apply the following operations: 
- Choose subarray nums[0, ..., 0]. nums[0] is the only element in this subarray. Hence, we multiply the score by nums[0]. The score becomes 1 * 19 = 19.
- Choose subarray nums[5, ..., 5]. nums[5] is the only element in this subarray. Hence, we multiply the score by nums[5]. The score becomes 19 * 18 = 342.
- Choose subarray nums[2, ..., 3]. Both nums[2] and nums[3] have a prime score of 2, but nums[2] has the smaller index. Hence, we multipy the score by nums[2]. The score becomes 342 * 14 = 4788.
It can be proven that 4788 is the highest score one can obtain.

Constraints:

  • 1 <= nums.length == n <= 105
  • 1 <= nums[i] <= 105
  • 1 <= k <= min(n * (n + 1) / 2, 109)

Approach overview

Problem Overview: You are given an array and can perform up to k operations. In each operation, you select a subarray and multiply the result by the element with the highest prime score (number of distinct prime factors). The goal is to maximize the final product modulo 1e9+7.

Approach 1: Dynamic Programming for Subarray Optimization (O(n^2) time, O(n) space)

This approach explicitly evaluates subarrays and keeps track of the best score contribution for each possible operation. You compute the prime score for every element, then iterate through possible subarray ranges while updating the maximum achievable product. A DP array tracks optimal results after selecting subarrays up to a given index. While conceptually straightforward, the nested iteration over subarrays makes this approach expensive for large inputs.

Approach 2: Sort by Prime Score for Optimized Selection (O(n log n) time, O(n) space)

The optimal solution relies on a greedy strategy combined with a monotonic stack. First compute the prime score (number of distinct prime factors) for each value using a number theory factorization method. Then determine how many subarrays treat each element as the dominant prime score using a stack to find the previous and next greater prime score indices. This gives the number of subarrays where the element contributes to the score.

Next, sort elements by value in descending order. For each element, determine how many times it can be used based on its subarray contribution and remaining k. Multiply the result by value^count using fast modular exponentiation. This greedy selection ensures the largest values contribute first, maximizing the product.

Recommended for interviews: Interviewers expect the greedy solution with a monotonic stack. The DP approach demonstrates understanding of the problem space, but the optimized method shows stronger algorithmic skill by combining array processing, stack-based span calculation, and prime factor analysis.

Approach 1: Sort by Prime Score for Optimized Selection

This approach focuses on selecting elements based on their prime scores to maximize scoring efficiently. The idea is to first compute the prime score for each element in the array. We then sort the elements by these scores, and for equal scores, by their indices. Finally, we choose the top elements with the highest prime scores for up to k operations.

def prime_factors_count(num):
    count = 0
    i = 2
    while i * i <= num:
        if num % i == 0:
            count += 1
            while num % i == 0:
                num //= i
        i += 1
    if num > 1:
        count += 1
    return count


def max_score(nums, k):
    MOD = 1000000007
    details = [(val, prime_factors_count(val), idx) for idx, val in enumerate(nums)]
    details.sort(key=lambda x: (-x[1], x[2]))
    score = 1
    for i in range(min(k, len(details))):
        score = (score * details[i][0]) % MOD
    return score


nums = [19, 12, 14, 6, 10, 18]
k = 3
print(max_score(nums, k))
import java.util.*;

public class MaxScore {
    private static final int MOD = 1000000007;

    private static int primeFactorsCount(int num) {
        int count = 0;
        for (int i = 2; i * i <= num; ++i) {
            if (num % i == 0) {
                ++count;
                while (num % i == 0) num /= i;
            }
        }
        if (num > 1) ++count;
        return count;
    }

    public static long maxScore(int[] nums, int k) {
        List<int[]> details = new ArrayList<>(); // Value, prime score, index
        for (int i = 0; i < nums.length; ++i) {
            details.add(new int[]{nums[i], primeFactorsCount(nums[i]), i});
        }

        details.sort((a, b) -> {
            if (a[1] != b[1]) return b[1] - a[1];
            return a[2] - b[2];
        });

        long score = 1;
        for (int i = 0; i < k; ++i) {
            score = (score * details.get(i)[0]) % MOD;
        }
        return score;
    }

    public static void main(String[] args) {
        int[] nums = {19, 12, 14, 6, 10, 18};
        int k = 3;
        System.out.println(maxScore(nums, k));
    }
}
#include <iostream>
#include <vector>
#include <algorithm>
#define MOD 1000000007

using namespace std;

int primeFactorsCount(int num) {
    int count = 0;
    for (int i = 2; i * i <= num; ++i) {
        if (num % i == 0) {
            ++count;
            while (num % i == 0) num /= i;
        }
    }
    if (num > 1) ++count;
    return count;
}

long long maxScore(vector<int>& nums, int k) {
    vector<tuple<int, int, int>> details; // Value, prime score, index
    for (int i = 0; i < nums.size(); ++i) {
        details.emplace_back(nums[i], primeFactorsCount(nums[i]), i);
    }

    sort(details.begin(), details.end(), [&](auto& a, auto& b) {
        if (get<1>(a) != get<1>(b))
            return get<1>(a) > get<1>(b);
        return get<2>(a) < get<2>(b);
    });

    long long score = 1;
    for (int i = 0; i < k; ++i) {
        score = (score * get<0>(details[i])) % MOD;
    }
    return score;
}

int main() {
    vector<int> nums = {19, 12, 14, 6, 10, 18};
    int k = 3;
    cout << maxScore(nums, k) << endl;
    return 0;
}
function primeFactorsCount(num) {
    let count = 0;
    for (let i = 2; i * i <= num; ++i) {
        if (num % i === 0) {
            ++count;
            while (num % i === 0) num = Math.floor(num / i);
        }
    }
    if (num > 1) ++count;
    return count;
}

function maxScore(nums, k) {
    const MOD = 1000000007;
    const details = nums.map((num, idx) => ({ value: num, score: primeFactorsCount(num), index: idx }));
    details.sort((a, b) => b.score - a.score || a.index - b.index);

    let score = 1;
    for (let i = 0; i < Math.min(k, details.length); i++) {
        score = (score * details[i].value) % MOD;
    }
    return score;
}

const nums = [19, 12, 14, 6, 10, 18];
const k = 3;
console.log(maxScore(nums, k));
#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000007

int primeFactorsCount(int num) {
    int count = 0;
    for (int i = 2; i * i <= num; ++i) {
        if (num % i == 0) {
            ++count;
            while (num % i == 0) num /= i;
        }
    }
    if (num > 1) ++count;
    return count;
}

int compare(const void* a, const void* b) {
    int* a_val = (int*)a;
    int* b_val = (int*)b;
    if (a_val[1] != b_val[1])
        return b_val[1] - a_val[1];
    return a_val[2] - b_val[2];
}

long long maxScore(int* nums, int numsSize, int k) {
    int details[numsSize][3]; // Value, prime score, index
    for (int i = 0; i < numsSize; i++) {
        details[i][0] = nums[i];
        details[i][1] = primeFactorsCount(nums[i]);
        details[i][2] = i;
    }

    qsort(details, numsSize, sizeof(details[0]), compare);

    long long score = 1;
    for (int i = 0; i < k && i < numsSize; i++) {
        score = (score * details[i][0]) % MOD;
    }
    return score;
}

int main() {
    int nums[] = {19, 12, 14, 6, 10, 18};
    int k = 3;
    int n = sizeof(nums) / sizeof(nums[0]);
    printf("%lld", maxScore(nums, n, k));
    return 0;
}
using System;
using System.Collections.Generic;

class MaxScore {
    private static int MOD = 1000000007;

    static int PrimeFactorsCount(int num) {
        int count = 0;
        for (int i = 2; i * i <= num; ++i) {
            if (num % i == 0) {
                ++count;
                while (num % i == 0) num /= i;
            }
        }
        if (num > 1) ++count;
        return count;
    }

    public static long MaximizeScore(int[] nums, int k) {
        List<(int value, int primeScore, int index)> details = new List<(int, int, int)>();
        for (int i = 0; i < nums.Length; i++) {
            details.Add((nums[i], PrimeFactorsCount(nums[i]), i));
        }

        details.Sort((a, b) => {
            if (a.primeScore != b.primeScore)
                return b.primeScore.CompareTo(a.primeScore);
            return a.index.CompareTo(b.index);
        });

        long score = 1;
        for (int i = 0; i < k && i < details.Count; i++) {
            score = (score * details[i].value) % MOD;
        }
        return score;
    }

    static void Main(string[] args) {
        int[] nums = { 19, 12, 14, 6, 10, 18 };
        int k = 3;
        Console.WriteLine(MaximizeScore(nums, k));
    }
}

In Python, list comprehensions and lambda sorting simplify the task of organizing element details. The approach calculates the score as intended, leveraging sorted tuples for efficiency.

Complexity

Time Complexity: O(n log n) primarily due to sorting.

Space Complexity: O(n) for maintaining detailed tuples for each element.

Try this approach in the editor

Approach 2: Dynamic Programming for Subarray Optimization

This method utilizes a dynamic programming approach to iteratively build up solutions. By keeping track of subarray scores using existing results, the approach can optimize the solution selection across available operations.

def prime_factors_count(num):
    count = 0
    i = 2
    while i * i <= num:
        if num % i == 0:
            count += 1
            while num % i == 0:
                num //= i
        i += 1
    if num > 1:
        count += 1
    return count


def max_score(nums, k):
    n = len(nums)
    MOD = 1000000007
    dp = [0] * (n + 1)
    dp[0] = 1

    for ops in range(1, k + 1):
        for i in range(n, 0, -1):
            max_prime_score_index = -1
            max_prime_score = -1
            for j in range(i):
                prime_score = prime_factors_count(nums[j])
                if prime_score > max_prime_score or (prime_score == max_prime_score and max_prime_score_index > j):
                    max_prime_score = prime_score
                    max_prime_score_index = j
            if max_prime_score_index != -1:
                dp[i] = (dp[i] + (dp[i - 1] * nums[max_prime_score_index]) % MOD) % MOD

    return dp[n]


nums = [19, 12, 14, 6, 10, 18]
k = 3
print(max_score(nums, k))
import java.util.*;

public class MaxScore {
    private static final int MOD = 1000000007;

    private static int primeFactorsCount(int num) {
        int count = 0;
        for (int i = 2; i * i <= num; ++i) {
            if (num % i == 0) {
                ++count;
                while (num % i == 0) num /= i;
            }
        }
        if (num > 1) ++count;
        return count;
    }

    public static long maxScore(int[] nums, int k) {
        int n = nums.length;
        long[] dp = new long[n + 1];
        dp[0] = 1;

        for (int ops = 1; ops <= k; ++ops) {
            for (int i = n; i > 0; --i) {
                int maxPrimeScoreIndex = -1, maxPrimeScore = -1;
                for (int j = 0; j < i; j++) {
                    int primeScore = primeFactorsCount(nums[j]);
                    if (primeScore > maxPrimeScore || (primeScore == maxPrimeScore && maxPrimeScoreIndex > j)) {
                        maxPrimeScore = primeScore;
                        maxPrimeScoreIndex = j;
                    }
                }
                if(maxPrimeScoreIndex != -1)
                    dp[i] = (dp[i] + (dp[i - 1] * nums[maxPrimeScoreIndex]) % MOD) % MOD;
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        int[] nums = {19, 12, 14, 6, 10, 18};
        int k = 3;
        System.out.println(maxScore(nums, k));
    }
}
#include <iostream>
#include <vector>
#define MOD 1000000007

using namespace std;

int primeFactorsCount(int num) {
    int count = 0;
    for (int i = 2; i * i <= num; ++i) {
        if (num % i == 0) {
            ++count;
            while (num % i == 0) num /= i;
        }
    }
    if (num > 1) ++count;
    return count;
}

long long maxScore(vector<int>& nums, int k) {
    int n = nums.size();
    vector<long long> dp(n + 1, 0);
    dp[0] = 1;

    for (int ops = 1; ops <= k; ++ops) {
        for (int i = n; i > 0; --i) {
            int maxPrimeScoreIndex = -1, maxPrimeScore = -1;
            for (int j = 0; j < i; ++j) {
                int primeScore = primeFactorsCount(nums[j]);
                if (primeScore > maxPrimeScore || (primeScore == maxPrimeScore && maxPrimeScoreIndex > j)) {
                    maxPrimeScore = primeScore;
                    maxPrimeScoreIndex = j;
                }
            }
            if(maxPrimeScoreIndex != -1)
                dp[i] = (dp[i] + (dp[i - 1] * nums[maxPrimeScoreIndex]) % MOD) % MOD;
        }
    }
    return dp[n];
}

int main() {
    vector<int> nums = {19, 12, 14, 6, 10, 18};
    int k = 3;
    cout << maxScore(nums, k) << endl;
    return 0;
}
function primeFactorsCount(num) {
    let count = 0;
    for (let i = 2; i * i <= num; ++i) {
        if (num % i === 0) {
            ++count;
            while (num % i === 0) num = Math.floor(num / i);
        }
    }
    if (num > 1) ++count;
    return count;
}

function maxScore(nums, k) {
    const MOD = 1000000007;
    const n = nums.length;
    const dp = Array(n + 1).fill(0);
    dp[0] = 1;

    for (let ops = 1; ops <= k; ops++) {
        for (let i = n; i > 0; --i) {
            let maxPrimeScoreIndex = -1;
            let maxPrimeScore = -1;
            for (let j = 0; j < i; ++j) {
                const primeScore = primeFactorsCount(nums[j]);
                if (primeScore > maxPrimeScore || (primeScore === maxPrimeScore && maxPrimeScoreIndex > j)) {
                    maxPrimeScore = primeScore;
                    maxPrimeScoreIndex = j;
                }
            }
            if(maxPrimeScoreIndex !== -1)
                dp[i] = (dp[i] + (dp[i - 1] * nums[maxPrimeScoreIndex]) % MOD) % MOD;
        }
    }
    return dp[n];
}

const nums = [19, 12, 14, 6, 10, 18];
const k = 3;
console.log(maxScore(nums, k));
#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000007

int primeFactorsCount(int num) {
    int count = 0;
    for (int i = 2; i * i <= num; ++i) {
        if (num % i == 0) {
            ++count;
            while (num % i == 0) num /= i;
        }
    }
    if (num > 1) ++count;
    return count;
}

long long maxScore(int* nums, int n, int k) {
    int dp[n + 1];
    dp[0] = 1;
    for (int i = 1; i <= n; ++i) dp[i] = 0;

    for (int ops = 1; ops <= k; ++ops) {
        for (int i = n; i > 0; --i) {
            int maxPrimeScoreIndex = -1, maxPrimeScore = -1;
            for (int j = 0; j < i; ++j) {
                int primeScore = primeFactorsCount(nums[j]);
                if (primeScore > maxPrimeScore || (primeScore == maxPrimeScore && maxPrimeScoreIndex > j)) {
                    maxPrimeScore = primeScore;
                    maxPrimeScoreIndex = j;
                }
            }
            if(maxPrimeScoreIndex != -1)
                dp[i] = (dp[i] + (dp[i - 1] * nums[maxPrimeScoreIndex]) % MOD) % MOD;
        }
    }
    return dp[n];
}

int main() {
    int nums[] = {19, 12, 14, 6, 10, 18};
    int k = 3;
    int n = sizeof(nums) / sizeof(nums[0]);
    printf("%lld", maxScore(nums, n, k));
    return 0;
}
using System;

class MaxScore {
    private static int MOD = 1000000007;

    static int PrimeFactorsCount(int num) {
        int count = 0;
        for (int i = 2; i * i <= num; ++i) {
            if (num % i == 0) {
                ++count;
                while (num % i == 0) num /= i;
            }
        }
        if (num > 1) ++count;
        return count;
    }

    public static long MaximizeScore(int[] nums, int k) {
        int n = nums.Length;
        long[] dp = new long[n + 1];
        dp[0] = 1;

        for (int ops = 1; ops <= k; ++ops) {
            for (int i = n; i > 0; --i) {
                int maxPrimeScoreIndex = -1, maxPrimeScore = -1;
                for (int j = 0; j < i; ++j) {
                    int primeScore = PrimeFactorsCount(nums[j]);
                    if (primeScore > maxPrimeScore || (primeScore == maxPrimeScore && maxPrimeScoreIndex > j)) {
                        maxPrimeScore = primeScore;
                        maxPrimeScoreIndex = j;
                    }
                }
                if(maxPrimeScoreIndex != -1)
                    dp[i] = (dp[i] + (dp[i - 1] * nums[maxPrimeScoreIndex]) % MOD) % MOD;
            }
        }
        return dp[n];
    }

    static void Main(string[] args) {
        int[] nums = { 19, 12, 14, 6, 10, 18 };
        int k = 3;
        Console.WriteLine(MaximizeScore(nums, k));
    }
}

Python's similar to exploring subarray combinations via dynamic programming, retaining decision-making efficiency over several passes.

Complexity

Time Complexity: O(n^2 * m^(1/2)), illustrating the in-depth exploration required.

Space Complexity: O(n) due to the DP array containing interim solutions.

Try this approach in the editor

Approach 3: Monotonic Stack + Greedy

It is not difficult to see that the number of subarrays with the highest prime score of an element nums[i] is cnt = (i - l) times (r - i), where l is the leftmost index such that primeScore(nums[l]) \ge primeScore(nums[i]), and r is the rightmost index such that primeScore(nums[r]) \ge primeScore(nums[i]).

Since we are allowed to operate at most k times, we can greedily enumerate nums[i] from large to small, and compute the cnt of each element. If cnt \le k, then the contribution of nums[i] to the answer is nums[i]^{cnt}, and we update k = k - cnt. If cnt \gt k, then the contribution of nums[i] to the answer is nums[i]^{k}, and we break out the loop.

Return the answer after the loop. Note that the power is large, so we need to use fast power.

The time complexity is O(n times log n), and the space complexity is O(n). Where n is the length of the array.

function maximumScore(nums: number[], k: number): number {
    const mod = 10 ** 9 + 7;
    const n = nums.length;
    const arr: number[][] = Array(n)
        .fill(0)
        .map(() => Array(3).fill(0));
    const left: number[] = Array(n).fill(-1);
    const right: number[] = Array(n).fill(n);
    for (let i = 0; i < n; ++i) {
        arr[i] = [i, primeFactors(nums[i]), nums[i]];
    }
    const stk: number[] = [];
    for (const [i, f, _] of arr) {
        while (stk.length && arr[stk.at(-1)!][1] < f) {
            stk.pop();
        }
        if (stk.length) {
            left[i] = stk.at(-1)!;
        }
        stk.push(i);
    }
    stk.length = 0;
    for (let i = n - 1; i >= 0; --i) {
        const f = arr[i][1];
        while (stk.length && arr[stk.at(-1)!][1] <= f) {
            stk.pop();
        }
        if (stk.length) {
            right[i] = stk.at(-1)!;
        }
        stk.push(i);
    }
    arr.sort((a, b) => b[2] - a[2]);
    let ans = 1n;
    for (const [i, _, x] of arr) {
        const l = left[i];
        const r = right[i];
        const cnt = (i - l) * (r - i);
        if (cnt <= k) {
            ans = (ans * qpow(BigInt(x), cnt, mod)) % BigInt(mod);
            k -= cnt;
        } else {
            ans = (ans * qpow(BigInt(x), k, mod)) % BigInt(mod);
            break;
        }
    }
    return Number(ans);
}

function primeFactors(n: number): number {
    let i = 2;
    const s: Set<number> = new Set();
    while (i * i <= n) {
        while (n % i === 0) {
            s.add(i);
            n = Math.floor(n / i);
        }
        ++i;
    }
    if (n > 1) {
        s.add(n);
    }
    return s.size;
}

function qpow(a: bigint, n: number, mod: number): bigint {
    let ans = 1n;
    for (; n; n >>>= 1) {
        if (n & 1) {
            ans = (ans * a) % BigInt(mod);
        }
        a = (a * a) % BigInt(mod);
    }
    return ans;
}
func maximumScore(nums []int, k int) int {
	n := len(nums)
	const mod = 1e9 + 7
	qpow := func(a, n int) int {
		ans := 1
		for ; n > 0; n >>= 1 {
			if n&1 == 1 {
				ans = ans * a % mod
			}
			a = a * a % mod
		}
		return ans
	}
	arr := make([][3]int, n)
	left := make([]int, n)
	right := make([]int, n)
	for i, x := range nums {
		left[i] = -1
		right[i] = n
		arr[i] = [3]int{i, primeFactors(x), x}
	}
	stk := []int{}
	for _, e := range arr {
		i, f := e[0], e[1]
		for len(stk) > 0 && arr[stk[len(stk)-1]][1] < f {
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			left[i] = stk[len(stk)-1]
		}
		stk = append(stk, i)
	}
	stk = []int{}
	for i := n - 1; i >= 0; i-- {
		f := arr[i][1]
		for len(stk) > 0 && arr[stk[len(stk)-1]][1] <= f {
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			right[i] = stk[len(stk)-1]
		}
		stk = append(stk, i)
	}
	sort.Slice(arr, func(i, j int) bool { return arr[i][2] > arr[j][2] })
	ans := 1
	for _, e := range arr {
		i, x := e[0], e[2]
		l, r := left[i], right[i]
		cnt := (i - l) * (r - i)
		if cnt <= k {
			ans = ans * qpow(x, cnt) % mod
			k -= cnt
		} else {
			ans = ans * qpow(x, k) % mod
			break
		}
	}
	return ans
}

func primeFactors(n int) int {
	i := 2
	ans := map[int]bool{}
	for i <= n/i {
		for n%i == 0 {
			ans[i] = true
			n /= i
		}
		i++
	}
	if n > 1 {
		ans[n] = true
	}
	return len(ans)
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Sort by Prime Score for Optimized Selection

Time Complexity: O(n log n) primarily due to sorting.

Space Complexity: O(n) for maintaining detailed tuples for each element.

Dynamic Programming for Subarray Optimization

Time Complexity: O(n^2 * m^(1/2)), illustrating the in-depth exploration required.

Space Complexity: O(n) due to the DP array containing interim solutions.

Monotonic Stack + Greedy–

Complexity analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming for Subarray OptimizationO(n^2)O(n)Useful for reasoning about subarray contributions or when constraints are small
Greedy with Prime Score + Monotonic StackO(n log n)O(n)Optimal approach for large arrays; calculates contribution spans and prioritizes largest values

Frequently asked questions

Is Apply Operations to Maximize Score easy or hard?

Apply Operations to Maximize Score is classified as Hard on LeetCode. The difficulty comes from combining number theory, monotonic stack span calculation, greedy ordering, and modular exponentiation into a single optimized solution.

Apply Operations to Maximize Score Python/Java solution

Python and Java implementations follow the same structure: compute prime scores, use a monotonic stack to calculate contribution spans, sort elements by value, and multiply contributions using modular exponentiation. The overall complexity remains O(n log n) in both languages.

How to solve Apply Operations to Maximize Score in O(n log n)?

Compute the prime score for each element using prime factorization. Use a monotonic stack to find the range of subarrays where each element has the highest prime score. Sort elements by value in descending order and greedily multiply their contribution using fast exponentiation until k operations are used.

What is the best approach for Apply Operations to Maximize Score?

The best approach uses a greedy strategy combined with a monotonic stack. First compute the prime score (number of distinct prime factors) for each element. Then calculate how many subarrays each element dominates using a stack to find previous and next greater prime scores. After sorting values in descending order, multiply contributions greedily until k operations are exhausted. This runs in O(n log n) time.

Is Apply Operations to Maximize Score asked at Google/Amazon/Meta?

Hard array and greedy problems involving monotonic stacks and number theory frequently appear in interviews at companies like Amazon, Google, and Meta. Variants testing stack-based span computation and greedy contribution counting are especially common.

What data structure is used in Apply Operations to Maximize Score?

The key data structure is a monotonic stack used to compute previous and next greater prime scores efficiently. Arrays store prime scores and contribution counts, while sorting supports the greedy selection phase.

What is the time complexity of Apply Operations to Maximize Score?

The optimal solution runs in O(n log n) time and O(n) space. O(n) is used to compute prime scores and monotonic stack spans, while O(n log n) comes from sorting elements by value for greedy selection.

Comments

Next problem · similarNext Greater Element IVHard
Now write it yourselfClose this page and solve Apply Operations to Maximize Score in the editor, without looking.
Practise Apply Operations to Maximize Score