Leetcode # 2818. Apply Operations to Maximize Score

https://leetcode.com/contest/weekly-contest-358/problems/apply-operations-to-maximize-score/

First Solution (Time Limit Exceeded)

Time Complexity: O(n * (A + n))
A := max(nums)
n := len(nums)
compute primes less than A: O(n * A)
compute dp: O(n * A + n ** 2)
Space Complexity: O(n ** 2)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def maximumScore(self, nums: List[int], k: int) -> int:
    dp = {}
    primes = [2]
    for i in range(len(nums)):
      num = nums[i]
      p = ps = 0
      while num > 1:
        # compute new primes
        if p == len(primes):
          prime = primes[-1] + 1
          while any(prime % _p == 0 for _p in primes): 
            prime += 1
          primes.append(prime)
   
        # compute prime score of nums[i:i]
        if num % primes[p] == 0:
          ps += 1
          while num % primes[p] == 0:
            num /= primes[p]
        else:
          p += 1
      dp[(i, i)] = (ps, nums[i])
    # compute dp[(i, j)]
    for l in range(2, len(nums) + 1):
      for i in range(len(nums) - l + 1):
        j = i + l - 1
        dp[(i, j)] = dp[(j, j)] \
                     if dp[(i, j - 1)][0] < dp[(j, j)][0] \
                     else dp[(i, j - 1)]

    # compute result
    result, MOD = 1, 10 ** 9 + 7
    sorted_ps = sorted([dp[rg][1] for rg in dp], reverse = True)
    for num in sorted_ps[0:k]:
      result = (result * num) % MOD
    return result

Second Solution (Time Limit Exceeded)

1. 求 number 是否為質數
   只需要驗證 [2, number^(1/2)] 間的整數
2. sorted(nums, reverse=True) = [N₁‘, N₂‘, …, N_n‘] (N_i‘ < N_j‘ if i < j)
   不必去算每個 N_i‘ 會出現在哪些 subarray
   而是從 N₁‘ 開始，算每個 N_i‘ 的subarray個數
   並計算 result ，直至執行 k 次乘算為止
3. pow(num, times, MOD) is much faster than (num ** times) % MOD

Time Complexity: O(n * isqrt(A) + n + k)
compute primes less than A ** (1 / 2): O(n * isqrt(A))
compute dp: O(n * A + n ** 2)execute k times multiplication: O(n * isqrt(A) + n  + k)
Space Complexity: O(isqrt(A) + n)
(The input and output generally do not count towards the space complexity.)

Last Updated on 2023/08/24 by A1go