Leetcode 2818. Apply Operations to Maximize Score

Jimmy   Mar 29, 2025   2354 words   ~60 mins
#Array #Math #Stack #Greedy #Sorting #Monotonic Stack #Number Theory

Table of Contents

Problem Informations

Problem Description

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 \times 2 \times 3 \times 5 \times 5$.

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

Since the answer may be large, return it modulo $10^9 + 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 \times 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 \times 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 \times 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 \times 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 multiply the score by nums[2]. The score becomes $342 \times 14 = 4788$.

It can be proven that 4788 is the highest score one can obtain.

Constraints:

  • $1 \leq \text{nums.length} = n \leq 10^5$
  • $1 \leq \text{nums}[i] \leq 10^5$
  • $1 \leq k \leq \min(n \times (n + 1) / 2, 10^9)$

Intuition

The problem requires maximizing a score by selecting subarrays and the element within those subarrays that has the highest prime score. The prime score is determined by counting distinct prime factors of a number. The main challenge is to choose subarrays and elements strategically to maximize the resulting score after at most k operations. Each operation should aim to increase the score as much as possible, leveraging the numbers within nums that have higher prime scores and can be chosen within the allowed constraints.

Approach

The solution employs a combination of mathematical techniques and strategic data structures to efficiently find the desired result. Here’s a step-by-step explanation of the approach:

  1. Prime Factorization and Score Calculation:
    For each number in the array nums, we determine its prime score, which is the count of distinct prime factors. This is achieved by factoring each number using Pollard’s Rho algorithm, which efficiently finds one non-trivial factor of a composite number. This factorization is repeated recursively until all factors are found. The distinct factors are then counted.

  2. Monotonic Stack for Segment Analysis:
    Two types of segment lengths are calculated for each index i in nums:

    • Max Segment Length Ending at i: Using a monotonic decreasing stack, we determine the maximum length of subarrays ending at each index where the current element has the highest prime score compared to subsequent elements.
    • Max Segment Length Starting at i: Similarly, using a monotonic increasing stack, we calculate the maximum length of subarrays starting at each index where the current element has a higher prime score compared to preceding elements.

  3. Combining Segment Information:
    Each position i in nums will have maximum segment length determined by multiplying the two segment lengths obtained from the above steps (one ending and one starting). This product captures the size of the segment where element nums[i] could potentially be the maximum prime score factor.

  4. Sorting and Selecting for Maximum Score:
    Construct a list of (value, index) pairs from nums, sorted by value in descending order. The rationale here is to prioritize larger numbers, as they will yield higher scores if they have the same prime score product opportunity.

  5. Compute Maximum Score with Modulo Consideration:
    Iterate through the sorted list, using each number the maximum number of times possible as dictated by the segment information while ensuring the total operations do not exceed k. Use modular multiplication and exponentiation to handle potential overflow and ensure results are within specified constraints (modulo $10^9 + 7$). Update the answer by multiplying with the currently considered number raised to the power of its allowable segment length.

  6. Output the Result:
    Return the computed score after considering as many operations as allowed, which maximizes the multiplication of selected elements based on their strategic placement and contribution to the score.

By organizing the problem into clear steps dealing with prime factorization, segment analysis, and strategic selection while considering numerical constraints and mathematical efficiency, the approach efficiently tackles the problem complexity and constraints.

Code

C++

typedef unsigned long long ull;

class Solution {
public:
    // Perform modular multiplication (using __int128 to avoid overflow)
    ull mod_mul(ull a, ull b, ull mod) {
        __uint128_t res = a;
        res *= b;
        return (ull)(res % mod);
    }

    // Perform modular exponentiation
    ull mod_pow(ull base, ull exp, ull mod) {
        ull result = 1;
        base %= mod;
        while (exp > 0) {
            if (exp & 1) result = mod_mul(result, base, mod);
            base = mod_mul(base, base, mod);
            exp >>= 1;
        }
        return result;
    }

    // Miller-Rabin primality test (suitable for 64-bit numbers)
    bool is_prime(ull n) {
        if (n < 2) return false;
        static int testPrimes[12] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
        for (int p : testPrimes) {
            if (n == (ull)p) return true;
            if (n % p == 0) return false;
        }
        ull d = n - 1;
        int s = 0;
        while ((d & 1ULL) == 0) {
            d >>= 1;
            s++;
        }
        int bases[7] = {2, 3, 5, 7, 11, 13, 17};
        for (int a : bases) {
            if ((ull)a % n == 0) continue;
            ull x = mod_pow(a, d, n);
            if (x == 1 || x == n - 1) continue;
            bool composite = true;
            for (int i = 1; i < s; i++) {
                x = mod_mul(x, x, n);
                if (x == n - 1) {
                    composite = false;
                    break;
                }
            }
            if (composite) return false;
        }
        return true;
    }

    // Pollard Rho algorithm for factorization
    ull pollard_rho(ull n) {
        if (n % 2ULL == 0) return 2;
        ull x = rand() % (n - 2) + 2;
        ull y = x;
        ull c = rand() % (n - 1) + 1;
        ull d = 1;
        while (d == 1) {
            x = (mod_mul(x, x, n) + c) % n;
            y = (mod_mul(y, y, n) + c) % n;
            y = (mod_mul(y, y, n) + c) % n;
            d = __gcd((ull)abs((long long)x - (long long)y), n);
            if (d == n) return pollard_rho(n);
        }
        return d;
    }

    // Recursive prime factorization, storing all prime factors (possibly repeated) in factors
    void factorize(ull n, vector<ull>& factors) {
        if (n == 1) return;
        if (is_prime(n)) {
            factors.push_back(n);
            return;
        }
        ull factor = pollard_rho(n);
        factorize(factor, factors);
        factorize(n / factor, factors);
    }

    // Calculate the prime score (number of distinct prime factors)
    int prime_score(ull n) {
        vector<ull> factors;
        factorize(n, factors);
        set<ull> distinct(factors.begin(), factors.end()); // Remove duplicates using a set
        return distinct.size();
    }

    // Function to compute minimum of two numbers
    long long min(long long a, long long b) { return a < b ? a : b; }

    // Function to compute the maximum possible score
    int maximumScore(vector<int>& nums, int k) {
        int n = nums.size();
        long long ans = 1;
        vector<long long> primeScores(n), maxSegmentLen(n);

        // Compute prime scores for each number in nums
        for (int i = 0; i < n; i++) primeScores[i] = prime_score(nums[i]);

        stack<long long> monotonicStack;
        maxSegmentLen[n - 1] = 1;
        monotonicStack.push(n - 1);

        // Determine maximum lengths of segments ending at each index
        for (int i = n - 2; i >= 0; i--) {
            while (!monotonicStack.empty() && primeScores[monotonicStack.top()] <= primeScores[i]) 
                monotonicStack.pop();

            maxSegmentLen[i] = monotonicStack.empty() ? n - i : monotonicStack.top() - i;
            monotonicStack.push(i);
        }

        // Clear the stack for reuse
        while (!monotonicStack.empty()) monotonicStack.pop();
        monotonicStack.push(0);

        // Determine maximum lengths of segments starting at each index
        for (int i = 1; i < n; i++) {
            while (!monotonicStack.empty() && primeScores[monotonicStack.top()] < primeScores[i]) 
                monotonicStack.pop();

            maxSegmentLen[i] *= (monotonicStack.empty() ? (i + 1) : (i - monotonicStack.top()));
            monotonicStack.push(i);
        }

        vector<pair<long long, long long>> sortedNums;
        for (int i = 0; i < n; i++) sortedNums.push_back({-nums[i], i});
        
        // Sort numbers (stored as negative values for descending order sorting of scores)
        sort(sortedNums.begin(), sortedNums.end());

        for (int i = 0; i < n; i++) {
            int count = min(maxSegmentLen[sortedNums[i].second], static_cast<long long>(k));
            ans = mod_mul(ans, mod_pow(-sortedNums[i].first, count, 1000000007ULL), 1000000007ULL);
            if (k <= maxSegmentLen[sortedNums[i].second]) break;
            k -= count;
        }
        return ans;
    }
};

Python

class Solution:
    from math import gcd
    from random import randrange
    
    # Perform modular multiplication
    def mod_mul(self, a, b, mod):
        return (a * b) % mod

    # Perform modular exponentiation
    def mod_pow(self, base, exp, mod):
        result = 1
        base %= mod
        while exp > 0:
            if exp & 1:
                result = self.mod_mul(result, base, mod)
            base = self.mod_mul(base, base, mod)
            exp >>= 1
        return result

    # Miller-Rabin primality test
    def is_prime(self, n):
        if n < 2:
            return False
        testPrimes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
        for p in testPrimes:
            if n == p:
                return True
            if n % p == 0:
                return False
        d = n - 1
        s = 0
        while (d & 1) == 0:
            d >>= 1
            s += 1
        bases = [2, 3, 5, 7, 11, 13, 17]
        for a in bases:
            if a % n == 0:
                continue
            x = self.mod_pow(a, d, n)
            if x == 1 or x == n - 1:
                continue
            composite = True
            for _ in range(1, s):
                x = self.mod_mul(x, x, n)
                if x == n - 1:
                    composite = False
                    break
            if composite:
                return False
        return True

    # Pollard Rho algorithm for factorization
    def pollard_rho(self, n):
        if n % 2 == 0:
            return 2
        x = self.randrange(2, n - 2)
        y = x
        c = self.randrange(1, n - 1)
        d = 1
        while d == 1:
            x = (self.mod_mul(x, x, n) + c) % n
            y = (self.mod_mul(y, y, n) + c) % n
            y = (self.mod_mul(y, y, n) + c) % n
            d = gcd(abs(x - y), n)
            if d == n:
                return self.pollard_rho(n)
        return d

    # Recursive prime factorization
    def factorize(self, n, factors):
        if n == 1:
            return
        if self.is_prime(n):
            factors.append(n)
            return
        factor = self.pollard_rho(n)
        self.factorize(factor, factors)
        self.factorize(n // factor, factors)

    # Calculate the prime score
    def prime_score(self, n):
        factors = []
        self.factorize(n, factors)
        return len(set(factors))  # Remove duplicates using a set

    # Function to compute the maximum possible score
    def maximumScore(self, nums, k):
        n = len(nums)
        ans = 1
        primeScores = [0] * n
        maxSegmentLen = [0] * n

        # Compute prime scores for each number in nums
        for i in range(n):
            primeScores[i] = self.prime_score(nums[i])

        monotonicStack = []
        maxSegmentLen[n - 1] = 1
        monotonicStack.append(n - 1)

        # Determine maximum lengths of segments ending at each index
        for i in range(n - 2, -1, -1):
            while monotonicStack and primeScores[monotonicStack[-1]] <= primeScores[i]:
                monotonicStack.pop()

            maxSegmentLen[i] = n - i if not monotonicStack else monotonicStack[-1] - i
            monotonicStack.append(i)

        monotonicStack.clear()
        monotonicStack.append(0)

        # Determine maximum lengths of segments starting at each index
        for i in range(1, n):
            while monotonicStack and primeScores[monotonicStack[-1]] < primeScores[i]:
                monotonicStack.pop()

            maxSegmentLen[i] *= i + 1 if not monotonicStack else i - monotonicStack[-1]
            monotonicStack.append(i)

        sortedNums = []
        for i in range(n):
            sortedNums.append((-nums[i], i))
        
        sortedNums.sort()

        for i in range(n):
            count = min(maxSegmentLen[sortedNums[i][1]], k)
            ans = self.mod_mul(ans, self.mod_pow(-sortedNums[i][0], count, 1000000007), 1000000007)
            if k <= maxSegmentLen[sortedNums[i][1]]:
                break
            k -= count

        return ans

Complexity

  • Time complexity: The overall time complexity is $O(n \log(\text{max\_val}) + n \log n)$.

    Explanation:

    • Prime Score Calculation: For each number in nums, we calculate the prime score by decomposing the number using prime factorization. The worst-case time complexity of prime factorization using Pollard’s Rho algorithm is approximately $O(\log^3 n)$ for each number. Since we are calculating this for all numbers in the array nums, this part contributes $O(n \log(\text{max\_val}))$, where max_val is the maximum possible value in nums.
    • Monotonic Stack Operations: The operations related to computing the maximum segment lengths using a monotonic stack are linear with respect to the number of elements in nums, i.e., $O(n)$ for both segment lengths ending and starting calculations.
    • Sorting: The sorted list of numbers is handled through a simple sort, which contributes $O(n \log n)$.
    • Final Computation: The final score computation involves iterating over elements in sortedNums, which is a linear operation $O(n)$ in the worst-case scenario, assuming k can be larger than any individual segment length.

    Combined, the time complexity is dominated by the prime score calculations and sorting, thus leading to $O(n \log(\text{max\_val}) + n \log n)$.

  • Space complexity: The overall space complexity is $O(n)$.

    Explanation:

    • Prime Score Calculation: Temporary storage for factors, which is not more than $O(\log n)$ for each number principle-wise for storage, but since this is done for each element in the array at a time, it can be considered constant space with respect to n.
    • Data Structures: The use of stacks and arrays like primeScores, maxSegmentLen, and sortedNums each require linear space with respect to the number of elements in nums, i.e., $O(n)$.
    • Overall, since linear-sized data structures dominate space usage, the space complexity remains $O(n)$.

Disclaimer: All reference materials on this website are sourced from the internet and are intended for learning purposes only. If you believe any content infringes upon your rights, please contact me at csnote.cc@gmail.com, and I will remove the relevant content promptly.


Feedback Welcome: If you notice any errors or areas for improvement in the articles, I warmly welcome your feedback and corrections. Your input will help this blog provide better learning resources. This is an ongoing process of learning and improvement, and your suggestions are valuable to me. You can reach me at csnote.cc@gmail.com.