We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Apply Operations to Maximize Score

Number: 3001

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

You are given an array of positive integers and an integer k. Starting with a score of 1, you can perform at most k operations. In each operation, you choose a non-empty subarray that has not been chosen before, then select the element from that subarray whose "prime score" (i.e. number of distinct prime factors) is the highest (if there is a tie, choose the one with the smallest index), and multiply your current score by that element. Return the maximum possible score modulo 10^9+7.

Key Insights

  • Transforming the problem: Instead of simulating each subarray pick, count for each element the total number of subarrays where it would be chosen.
  • Use monotonic stacks to efficiently calculate the “span” (left and right boundaries) where an element’s prime score is dominant.
  • Compute the weight (frequency) for each element as the product of its left and right spans.
  • Greedily multiplying by the largest numbers first maximizes the overall product.
  • Use fast exponentiation and modular arithmetic to handle large exponents and mod operations.

Space and Time Complexity

Time Complexity: O(n log n), due to prime factorization for numbers up to 10^5 and sorting the candidate pairs. Space Complexity: O(n), for storing prime scores, spans, and candidate pairs.

Solution

  1. Precompute the smallest prime factors (spf) for all numbers up to the maximum value in the array using the sieve method.
  2. For each number in the array, calculate its prime score (the number of distinct prime factors).
  3. Use two monotonic stacks to compute for every element its left and right spans:
    • Left span indicates the number of subarrays ending at the current element where it is the dominant candidate.
    • Right span indicates the number of subarrays starting at the current element where it remains dominant.
  4. The frequency (number of subarrays where an element is chosen) is the product of its left and right spans.
  5. Create a list of (value, frequency) pairs and sort them in descending order by value.
  6. Iterate through the list and greedily “use” each element as many times as possible (up to its frequency or remaining operations k), multiplying the result accordingly (using fast modular exponentiation).
  7. Return the final score modulo 10^9+7.

Code Solutions

MOD = 10**9 + 7

# Sieve to precompute smallest prime factors (spf)
def sieve(max_num):
    spf = list(range(max_num + 1))
    for i in range(2, int(max_num**0.5) + 1):
        if spf[i] == i:
            for j in range(i*i, max_num + 1, i):
                if spf[j] == j:
                    spf[j] = i
    return spf

# Compute the prime score for x (number of distinct prime factors)
def prime_score(x, spf):
    count = 0
    prev = -1
    while x > 1:
        factor = spf[x]
        if factor != prev:
            count += 1
            prev = factor
        x //= factor
    return count

def maxScore(nums, k):
    n = len(nums)
    max_num = max(nums)
    spf = sieve(max_num)
    
    # Calculate prime scores for each element in nums
    scores = [prime_score(x, spf) for x in nums]
    
    left = [0] * n
    right = [0] * n
    stack = []
    
    # Compute left span: number of subarrays ending at i where nums[i] is dominant
    for i in range(n):
        while stack and (scores[stack[-1]] < scores[i] or (scores[stack[-1]] == scores[i] and nums[stack[-1]] <= nums[i])):
            stack.pop()
        left[i] = i + 1 if not stack else i - stack[-1]
        stack.append(i)
    
    stack.clear()
    # Compute right span: number of subarrays starting at i where nums[i] remains dominant
    for i in range(n - 1, -1, -1):
        while stack and (scores[stack[-1]] <= scores[i]):
            stack.pop()
        right[i] = n - i if not stack else stack[-1] - i
        stack.append(i)
    
    # Build (value, frequency) pairs where frequency = left * right
    pairs = []
    for i in range(n):
        frequency = left[i] * right[i]
        pairs.append((nums[i], frequency))
    
    # Sort pairs in descending order by value
    pairs.sort(key=lambda x: x[0], reverse=True)
    
    result = 1
    remaining = k
    for value, freq in pairs:
        if remaining <= 0:
            break
        use = min(remaining, freq)
        result = (result * pow(value, use, MOD)) % MOD
        remaining -= use
    return result

# Example usage:
nums1 = [8, 3, 9, 3, 8]
k1 = 2
print(maxScore(nums1, k1))  # Expected output: 81

nums2 = [19, 12, 14, 6, 10, 18]
k2 = 3
print(maxScore(nums2, k2))  # Expected output: 4788
← Back to All Questions