🚀 [2818. Apply Operations to Maximize Score] - Hard 🔥

[Antim-IWP]

🚀 [2818. Apply Operations to Maximize Score] - Hard 🔥

Problem Statement:

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:

1. Choose any non-empty subarray nums[l, ..., r] that you haven't chosen previously.
2. 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.
3. Multiply your current score by x.

🔹 Definition:
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 (distinct primes: {2, 3, 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:  
- Choose subarray nums[2, ..., 2]. nums[2] is the only element in this subarray.  
  Multiply the score by nums[2]. Score = 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. Multiply the score by nums[2].  
  Score = 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:  
- Choose subarray nums[0, ..., 0]. Multiply by nums[0]. Score = 1 × 19 = 19.  
- Choose subarray nums[5, ..., 5]. Multiply by nums[5]. Score = 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. Multiply by nums[2].  
  Score = 342 × 14 = 4788.  
🔹 It can be proven that `4788` is the highest score one can obtain.

---

🔹 Constraints:

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

---

💡 Discussion Topics:

1. What would be an efficient way to calculate the prime score of numbers up to 10^5?
2. How can we efficiently find the best subarray and element to multiply the score?
3. Would a greedy approach or priority queue help in solving this problem?
4. What is the time complexity of your solution?

---

Feel free to share your approaches, ideas, and solutions below! Let's discuss and optimize together! 🔥🚀

[iamAntimPal]

Thank you for this discussition solution is here Click For Solution

import math
from heapq import nlargest
from collections import defaultdict

MOD = 10**9 + 7

def count_prime_factors(n):
    """Returns the number of distinct prime factors of n."""
    factors = set()
    for i in range(2, int(math.sqrt(n)) + 1):
        while n % i == 0:
            factors.add(i)
            n //= i
    if n > 1:
        factors.add(n)
    return len(factors)

def precompute_prime_scores(limit=10**5):
    """Precomputes the prime scores for numbers from 1 to limit."""
    prime_scores = [0] * (limit + 1)
    
    for i in range(2, limit + 1):
        if prime_scores[i] == 0:  # `i` is a prime
            for j in range(i, limit + 1, i):
                prime_scores[j] += 1  # Mark multiples of `i`
    
    return prime_scores

def maxScore(nums, k):
    """Computes the maximum score using `k` operations."""
    prime_scores = precompute_prime_scores(max(nums))

    # Store elements as (prime_score, value, index)
    elements = []
    
    for i, num in enumerate(nums):
        elements.append((prime_scores[num], num, i))
    
    # Sort by (prime_score descending, value descending, index ascending)
    elements.sort(reverse=True, key=lambda x: (x[0], x[1], -x[2]))

    # Take `k` highest scoring elements
    result = 1
    for _, value, _ in elements[:k]:
        result = (result * value) % MOD

    return result

[Antim-IWP]

thank you