2818. Apply Operations to Maximize Score

HardStackGreedyArrayMathNumber TheoryMonotonic Stack
Leetcode Link

Problem Description

In this problem, you are provided with two primary inputs: An array nums containing n positive integers and an integer k, which represents the maximum number of operations you can apply. Your goal is to maximize a score, which starts at 1, by performing a series of operations on the nums array.

Each operation consists of the following steps:

  • First, you select a non-empty subarray from nums that you haven't chosen before.
  • Then, within that subarray, you find the element with the highest prime score. The prime score is defined as the count of distinct prime factors of a number. If multiple elements share the highest prime score, you choose the one with the smallest index within the subarray.
  • Finally, you multiply your current score by the selected element.

You can repeat this operation at most k times. The challenge is to calculate the maximum possible score you can achieve after performing up to k operations. Due to the fact that the final score can be quite large, the result should be returned modulo 10^9 + 7.

Intuition

To arrive at the solution, it's pivotal to understand a couple of concepts. Firstly, the 'prime score' becomes a significant factor in determining the value you will multiply your score with. Since you aim to maximize your score, you're naturally inclined to select elements with higher prime scores.

Secondly, we need to consider the number of subarrays an element can be a part of while having the highest prime score, since this will affect the frequency with which that element's value can be used to multiply the score. Specifically, each number nums[i] contributes to the score as nums[i]^cnt (where cnt is the count of subarrays it's the highest prime score of). This count cnt can be determined using the boundaries l and r, which are the farthest indices where the prime score does not exceed that of nums[i].

With these key observations, the solution employs a greedy approach. It suggests sorting elements in descending order based on their values since higher numbers are likely to have a higher prime score and hence contribute more significantly to maximizing the score. While processing the sorted elements, we calculate the cnt for each and if cnt is less than or equal to k, we incorporate that element's contribution (nums[i]^cnt) into the total score. If cnt exceeds k, we take the contribution as nums[i]^k instead, and then stop, since we've used up all k operations.

A monotonic stack is used to efficiently find the leftmost and rightmost indexes l and r to calculate cnt for each element. This helps to maintain a running track of the prime scores in a way that allows quick look-ups of the needed boundaries.

Finally, the solution applies a fast power algorithm while taking the modulo at each step to ensure the answer stays within bounds, considering the potential size of the number due to repeated multiplication.

Learn more about Stack, Greedy, Math and Monotonic Stack patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Solution Approach

To implement the solution, we use two important techniques: a greedy approach and a monotonic stack.

The prime factors function primeFactors(n) is first defined to calculate the number of distinct prime factors of n to determine the prime score of each number in the given array nums.

Then, in the maximumScore method of Solution, we begin by preparing an array arr which contains tuples for each element in nums. Each tuple consists of the index of the element, the prime score obtained from primeFactors function, and the element's value itself.

To efficiently calculate the leftmost (l) and rightmost (r) boundaries where an element nums[i] has the highest prime score in subarrays, we leverage a monotonic stack. A monotonic stack is a stack where the elements are always in increasing or decreasing order. We maintain two stacks to determine the indices l and r.

  • The left array is filled by iterating through arr from the beginning, and we use a stack to track the first previous element with a prime score not less than the current element's prime score.
  • The right array is filled by iterating through arr in reverse, maintaining a stack to track the next element with a prime score not less than the current element's prime score.

In both processes, if the current element's prime score is higher than the one on the top of the stack, we pop elements from the stack because we're only interested in the closest boundaries that have a higher or equal prime score.

After determining the left and right bounds for each element, we sort the array arr by the element's value in decreasing order, since we want to use the largest elements first to maximize the score.

We then iterate over this sorted array. For each element nums[i], we calculate the count cnt as the product of the distance from l to i and the distance from i to r. This count represents the number of subarrays where nums[i] is the maximum prime score that hasn't been picked yet.

We check if cnt is less than or equal to k, and if so, we update our score by multiplying it by nums[i]^cnt, and decrement k by cnt. If cnt is greater than k, we multiply our score by nums[i]^k, as we can only perform k more operations, and then we break out of the loop.

Lastly, we return the score modulo 10^9 + 7. The power function in Python (pow(base, exp, mod)) is used to handle the large exponents and perform modulus at the same time for efficiency, reducing the computational complexity.

By following this approach, we ensure a greedy selection of elements translates into a maximum score, bounded by the number of times k we can perform the operation, and make use of efficient data structures and algorithms to handle the constraints of the problem.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement recursion?

Example Walkthrough

Let's take an example to illustrate the solution approach. Suppose we have an array nums with values [6, 12, 5], and k equals 2. The prime factors counts for these numbers are as follows: The number 6 has two distinct prime factors (2 and 3), 12 also has two distinct prime factors (2 and 3 as well), and 5 has one prime factor (5 itself).

Let's walk through the solution step by step:

  1. Determine the prime score for each element in nums:

    • 6 has 2 prime factors.
    • 12 has 2 prime factors.
    • 5 has 1 prime factor.

  2. Create a list arr that contains tuples of index, prime score, and the element's value:

    • [(0, 2, 6), (1, 2, 12), (2, 1, 5)]

  3. Initialize two monotonic stacks and arrays left and right to track the boundaries of subarrays:

    • On iterating from the start for left, we will not find any previous elements with a higher prime score, so each element gets a left value of -1.
    • On iterating from the end for right, we will not find any next elements with a higher prime score, so each element gets a right value of the length of nums.

  4. Sort arr based on the element's value in descending order:

    • [(1, 2, 12), (0, 2, 6), (2, 1, 5)]

  5. Calculate the count cnt for each element based on the left and right boundaries:

    • For element 12, cnt is (1 - (-1)) * (3 - 1) = 4.
    • For element 6, cnt would be (0 - (-1)) * (3 - 0) = 3, but since we already picked element 12, which includes this element in one of its subarrays, we don't include 6 in our calculation.
    • Element 5 is not considered since we will have used all operations by this point.

  6. Now use the element with a count cnt less than or equal to k to maximize the score:

    • Score starts at 1.
    • First, we pick the element 12 with a cnt of 4. Since k is 2, we multiply our score by 12^2 (modulo 10^9 + 7). Our score becomes 144 (as 12^2 = 144), and k is now 0.
    • We've used up all k operations, so we conclude with a final score of 144.

Thus, the solution to this example, following the approach described, yields a maximal score of 144 after performing at most k=2 operations.

Keep in mind that the actual implementation would handle much larger numbers and array sizes, efficiently managing the modulo operation and arithmetic, but the core steps would follow this logical sequence.

Solution Implementation

1from typing import List
2
3def prime_factors(n: int) -> int:
4    # Initialize the starting divisor and an empty set to store unique prime factors
5    divisor = 2
6    unique_prime_factors = set()
7  
8    # Loop to find prime factors
9    while divisor * divisor <= n:
10        while n % divisor == 0:
11            unique_prime_factors.add(divisor)
12            n //= divisor
13        divisor += 1
14      
15    # If there is a remaining prime factor larger than the square root of original n, add that too
16    if n > 1:
17        unique_prime_factors.add(n)
18  
19    # Return the count of unique prime factors
20    return len(unique_prime_factors)
21
22
23class Solution:
24    def maximum_score(self, nums: List[int], k: int) -> int:
25        mod = 10**9 + 7  # The modulo value given in the problem
26      
27        # Create an array that holds tuples of (index, number of prime factors, value) for each number
28        arr = [(index, prime_factors(x), x) for index, x in enumerate(nums)]
29        n = len(nums)  # The length of the provided nums list
30      
31        left_boundaries = [-1] * n  # Will hold the left boundaries for each number
32        right_boundaries = [n] * n  # Will hold the right boundaries for each number
33        stack = []  # Initialize an empty stack
34      
35        # Calculate left boundary for each element
36        for index, factors_count, value in arr:
37            while stack and stack[-1][0] < factors_count:
38                stack.pop()
39            if stack:
40                left_boundaries[index] = stack[-1][1]
41            stack.append((factors_count, index))
42      
43        stack.clear()  # Clear the stack for reuse
44      
45        # Calculate right boundary for each element, processing from the end to the front
46        for index, factors_count, value in reversed(arr):
47            while stack and stack[-1][0] <= factors_count:
48                stack.pop()
49            if stack:
50                right_boundaries[index] = stack[-1][1]
51            stack.append((factors_count, index))
52      
53        # Sort the array in decreasing order based on the value
54        arr.sort(key=lambda x: -x[2])
55      
56        answer = 1  # Initialize answer to 1 since we'll be multiplying
57        for index, factors_count, value in arr:
58            left_index, right_index = left_boundaries[index], right_boundaries[index]
59            count = (index - left_index) * (right_index - index)
60          
61            # If we can use the entire count within the limit k
62            if count <= k:
63                answer = answer * pow(value, count, mod) % mod
64                k -= count
65            else:
66                # Use only the remaining k increments and then break
67                answer = answer * pow(value, k, mod) % mod
68                break
69      
70        # Return the final answer modulo the given mod value
71        return answer
72
1import java.util.*;
2
3class Solution {
4    private final int MODULO = (int) 1e9 + 7;
5
6    public int maximumScore(List<Integer> nums, int k) {
7        int n = nums.size();
8        // Creating a 2D array to store index, number of prime factors, and the actual number
9        int[][] arr = new int[n][3];
10        for (int i = 0; i < n; ++i) {
11            arr[i] = new int[] {i, countPrimeFactors(nums.get(i)), nums.get(i)};
12        }
13        int[] left = new int[n];
14        int[] right = new int[n];
15        Arrays.fill(left, -1);
16        Arrays.fill(right, n);
17        Deque<Integer> stack = new ArrayDeque<>();
18        // Calculate left limits for every element
19        for (int i = 0; i < n; ++i) {
20            while (!stack.isEmpty() && arr[stack.peek()][1] < arr[i][1]) {
21                stack.pop();
22            }
23            if (!stack.isEmpty()) {
24                left[i] = stack.peek();
25            }
26            stack.push(i);
27        }
28        stack.clear();
29        // Calculate right limits for every element
30        for (int i = n - 1; i >= 0; --i) {
31            while (!stack.isEmpty() && arr[stack.peek()][1] <= arr[i][1]) {
32                stack.pop();
33            }
34            if (!stack.isEmpty()) {
35                right[i] = stack.peek();
36            }
37            stack.push(i);
38        }
39        // Sort the array in decreasing order of the actual number
40        Arrays.sort(arr, (a, b) -> b[2] - a[2]);
41        long answer = 1;
42        for (int[] elem : arr) {
43            int index = elem[0];
44            int value = elem[2];
45            int leftLimit = left[index];
46            int rightLimit = right[index];
47            long count = (long) (index - leftLimit) * (rightLimit - index);
48            if (count <= k) {
49                answer = answer * quickPower(value, count) % MODULO;
50                k -= count;
51            } else {
52                answer = answer * quickPower(value, k) % MODULO;
53                break;
54            }
55        }
56        return (int) answer;
57    }
58
59    // Count the number of distinct prime factors of a given number
60    private int countPrimeFactors(int number) {
61        int factor = 2;
62        Set<Integer> factors = new HashSet<>();
63        while (factor <= number / factor) {
64            while (number % factor == 0) {
65                factors.add(factor);
66                number /= factor;
67            }
68            ++factor;
69        }
70        if (number > 1) {
71            factors.add(number);
72        }
73        return factors.size();
74    }
75
76    // Calculate a to the power of n modulo MODULO
77    private int quickPower(long base, long exponent) {
78        long result = 1;
79        while (exponent > 0) {
80            if ((exponent & 1) == 1) {
81                result = result * base % MODULO;
82            }
83            base = base * base % MODULO;
84            exponent >>= 1;
85        }
86        return (int) result;
87    }
88}
89
1#include <vector>
2#include <stack>
3#include <tuple>
4#include <algorithm>
5#include <unordered_set>
6
7class Solution {
8public:
9    int maximumScore(vector<int>& nums, int k) {
10        const int MOD = 1e9 + 7; // Define the modulo constant
11        int n = nums.size(); // Get the size of the input array
12      
13        // Create a list of tuples to store the index, number of unique prime factors and the number itself
14        vector<tuple<int, int, int>> triples(n);
15        for (int i = 0; i < n; ++i) {
16            triples[i] = {i, primeFactors(nums[i]), nums[i]};
17        }
18      
19        // Initialize vectors to track the left and right bounds
20        vector<int> leftBounds(n, -1);
21        vector<int> rightBounds(n, n);
22        stack<int> monoStack; // Monotonic stack for processing
23      
24        // Process left bounds
25        for (const auto &[index, factorCount, _] : triples) {
26            while (!monoStack.empty() && get<1>(triples[monoStack.top()]) < factorCount) {
27                monoStack.pop();
28            }
29            if (!monoStack.empty()) {
30                leftBounds[index] = monoStack.top();
31            }
32            monoStack.push(index);
33        }
34      
35        monoStack = stack<int>(); // Reset the stack for right bounds processing
36        for (int i = n - 1; i >= 0; --i) {
37            int factorCount = get<1>(triples[i]);
38            while (!monoStack.empty() && get<1>(triples[monoStack.top()]) <= factorCount) {
39                monoStack.pop();
40            }
41            if (!monoStack.empty()) {
42                rightBounds[i] = monoStack.top();
43            }
44            monoStack.push(i);
45        }
46      
47        // Sort triples in decreasing order based on the values of the numbers
48        sort(triples.begin(), triples.end(), [](const auto& lhs, const auto& rhs) {
49            return get<2>(rhs) < get<2>(lhs);
50        });
51      
52        long long answer = 1; // Initialize the result
53      
54        // Helper lambda function for fast exponentiation under modulo
55        auto quickPow = [&](long long base, int exp) {
56            long long result = 1;
57            while (exp > 0) {
58                if (exp & 1) {
59                    result = result * base % MOD;
60                }
61                base = base * base % MOD;
62                exp >>= 1;
63            }
64            return result;
65        };
66      
67        // Calculate the final answer
68        for (const auto &[index, _, value] : triples) {
69            int l = leftBounds[index], r = rightBounds[index];
70            // Calculate the number of contiguous subarrays    
71            long long count = static_cast<long long>(index - l) * (r - index);
72            if (count <= k) {
73                answer = answer * quickPow(value, count) % MOD;
74                k -= count;
75            } else {
76                answer = answer * quickPow(value, k) % MOD;
77                break;
78            }
79        }
80      
81        return answer;
82    }
83
84    // Helper function to count unique prime factors of a number
85    int primeFactors(int n) {
86        int factor = 2;
87        unordered_set<int> uniquePrimeFactors;
88        while (factor <= n / factor) {
89            while (n % factor == 0) {
90                uniquePrimeFactors.insert(factor);
91                n /= factor;
92            }
93            ++factor;
94        }
95        if (n > 1) {
96            uniquePrimeFactors.insert(n);
97        }
98        return uniquePrimeFactors.size();
99    }
100};
101
1function maximumScore(nums: number[], k: number): number {
2    const MODULUS = 10 ** 9 + 7;
3    const lengthOfNums = nums.length;
4    const factorInfo: number[][] = Array(lengthOfNums)
5        .fill(0)
6        .map(() => Array(3).fill(0));
7    const nearestSmallerToLeft: number[] = Array(lengthOfNums).fill(-1);
8    const nearestSmallerToRight: number[] = Array(lengthOfNums).fill(lengthOfNums);
9  
10    // Filling 'factorInfo' with arrays containing the index, number of prime factors and value of each element in 'nums'
11    for (let i = 0; i < lengthOfNums; ++i) {
12        factorInfo[i] = [i, primeFactors(nums[i]), nums[i]];
13    }
14
15    const stack: number[] = [];
16    // Fill 'nearestSmallerToLeft' array with the nearest index to the left that has a smaller number of prime factors
17    for (const [index, numPrimeFactors, _] of factorInfo) {
18        while (stack.length && factorInfo[stack.at(-1)!][1] < numPrimeFactors) {
19            stack.pop();
20        }
21        if (stack.length) {
22            nearestSmallerToLeft[index] = stack.at(-1)!;
23        }
24        stack.push(index);
25    }
26
27    stack.length = 0;
28    // Fill 'nearestSmallerToRight' array with the nearest index to the right that has a smaller or equal number of prime factors
29    for (let i = lengthOfNums - 1; i >= 0; --i) {
30        const numPrimeFactors = factorInfo[i][1];
31        while (stack.length && factorInfo[stack.at(-1)!][1] <= numPrimeFactors) {
32            stack.pop();
33        }
34        if (stack.length) {
35            nearestSmallerToRight[i] = stack.at(-1)!;
36        }
37        stack.push(i);
38    }
39
40    // Sort 'factorInfo' in descending order by the value of the elements
41    factorInfo.sort((a, b) => b[2] - a[2]);
42
43    let answer = 1n;
44    // Compute the maximum score using the previously computed arrays
45    for (const [index, _, value] of factorInfo) {
46        const left = nearestSmallerToLeft[index];
47        const right = nearestSmallerToRight[index];
48        const count = (index - left) * (right - index);
49        if (count <= k) {
50            answer = (answer * qpow(BigInt(value), count, MODULUS)) % BigInt(MODULUS);
51            k -= count;
52        } else {
53            answer = (answer * qpow(BigInt(value), k, MODULUS)) % BigInt(MODULUS);
54            break;
55        }
56    }
57    return Number(answer);
58}
59
60// Find the number of distinct prime factors of the given number 'n'
61function primeFactors(n: number): number {
62    let currentFactor = 2;
63    const uniqueFactors: Set<number> = new Set();
64    while (currentFactor * currentFactor <= n) {
65        while (n % currentFactor === 0) {
66            uniqueFactors.add(currentFactor);
67            n = Math.floor(n / currentFactor);
68        }
69        ++currentFactor;
70    }
71    if (n > 1) {
72        uniqueFactors.add(n);
73    }
74    return uniqueFactors.size;
75}
76
77// Calculate 'a' to the power of 'n' modulo 'mod'
78function qpow(a: bigint, n: number, mod: number): bigint {
79    let result = 1n;
80    while (n > 0) {
81        if (n & 1) {
82            result = (result * a) % BigInt(mod);
83        }
84        a = (a * a) % BigInt(mod);
85        n >>>= 1;
86    }
87    return result;
88}
89
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is a min heap?

Time and Space Complexity

Time Complexity

The time complexity of the code consists of several parts:

  1. Calculating prime factors for each number in the nums list:

    • For each number x, the primeFactors function can go up to sqrt(x) which is the worst-case scenario. However, since the prime factors are only up to the square root of x, this part is typically less than O(n * sqrt(x)).
    • Across all numbers, since we can't assume the average value of x, if we treat the input array elements as having value up to m in the worst case, this part can be seen as O(n * sqrt(m)), where m is the maximum number in nums.

  2. Building the left and right arrays using a monotonically decreasing stack approach:

    • In usual stack operations (push/pop), each element is processed once, making this O(n).

  3. Sorting the transformed arr list based on the third element (the value of the number itself):

    • Sorting is typically O(n * log(n)).

  4. The final loop to calculate the answer:

    • The loop runs at most n times, and in each iteration, pow function is called which is generally O(log(x)) for each x. Since there can be up to n such calls, in the worst case, this part is O(n * log(m)) where m is the maximum number in nums (note that the exponentiation is modulo mod, which doesn't affect time complexity).

Combining these parts, the dominant term is from sorting and the pow operations, resulting in O(n * log(n) + n * log(m)). If m (the maximum element in nums) is on the same order as n or less, it simplifies to O(n * log(n)).

Space Complexity

The space complexity of the code consists of the following parts:

  1. The ans set inside primeFactors function has the space complexity that depends on the number of distinct prime factors. In the worst case, all numbers are distinct primes, so the set size can be O(sqrt(m)). However, since only one set is maintained at a time and is rewritten for each number, this doesn't scale with n.

  2. The arr list would store a tuple for each element in nums, resulting in O(n).

  3. The left and right arrays which are both of size n, together contribute O(2n).

  4. The stack stk which is used twice could size up to n elements in the worst case, contributing another O(n).

Combining these, the space complexity would be O(n) as the dominant term, conforming with the reference provided.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫