LeetCode, Hard: 2818. Apply Operations to Maximize Score. Swift

Sergey Leschev. LeetCode Global TOP 200.
Sergey Leschev. LeetCode Global TOP 200.

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 * 2 * 3 * 5 * 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 * 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 * 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 * 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 * 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 multipy the score by nums[2]. The score becomes 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)

Approach

1 Compute Prime Scores:

  • Calculate the prime score for each integer in the array nums. Prime score represents the number of distinct prime factors of an integer.
  • Initialize a boolean array prime of size upper, where upper is the maximum element in nums plus 1.
  • Initialize an integer array primeScore of the same size.
  • Set prime[0] and prime[1] to false.
  • Iterate over integers from 2 to upper - 1, and update primeScore and prime based on their prime factors.

2 Compute Next Greater Elements:

  • Initialize arrays nextGreaterElement and prevGreaterOrEqualElement of size n, where n is the length of nums.
  • Use a monotonic stack to find the next greater element with a greater prime score for each element in nums.
  • Iterate through nums and maintain a stack of indices.
  • For each element, pop elements from the stack if their prime score is less than or equal to the current element's prime score.
  • Record the index of the top of the stack as the nextGreaterElement if the stack is not empty, else set it to n.
  • Repeat the above process in reverse to compute prevGreaterOrEqualElement.

3 Sort and Process Elements:

  • Create an array of tuples (num, i) where num is the value of an element and i is its index in nums.
  • Sort the tuples in descending order of the first element (num).
  • Loop through the sorted tuples and perform the following steps:Compute the number of operations as the minimum of (i - prevGreaterOrEqualElement[i]) * (nextGreaterElement[i] - i) and k.Update res by multiplying it with pow(num, operations) modulo MOD using the helper function pow.Decrement k by the number of operations.If k becomes 0, return res.

4 Helper Function for Exponentiation:

  • Implement the pow function to calculate exponentiation efficiently using modular arithmetic.

Complexity

  • Time complexity: O(max(nums) * log(max(nums)) + n * log(n)). Accounting for computing prime scores, using the stack to compute next greater elements, and sorting the tuples.
  • Space complexity: O(max(nums) + n). Considering the space required for arrays and the stack used for computation.

Code (Swift)

class Solution { func maximumScore(_ nums: [Int], _ k: Int) -> Int { let MOD = 1_000_000_007 var k = k // Make a mutable copy of k let n = nums.count var upper = nums.max()! + 1 var prime = [Bool](repeating: true, count: upper) prime[0] = false prime[1] = false var primeScore = [Int](repeating: 0, count: upper) for i in 2..<upper { if prime[i] { var j = i while j < upper { primeScore[j] += 1 prime[j] = false j += i } } } var nextGreaterElement = [Int](repeating: n, count: n) var s = [Int]() for i in (0..<n).reversed() { while !s.isEmpty && primeScore[nums[i]] >= primeScore[nums[s.last!]] { s.popLast() } nextGreaterElement[i] = s.isEmpty ? n : s.last! s.append(i) } var prevGreaterOrEqualElement = [Int](repeating: -1, count: n) s.removeAll() for i in 0..<n { while !s.isEmpty && primeScore[nums[i]] > primeScore[nums[s.last!]] { s.popLast() } prevGreaterOrEqualElement[i] = s.isEmpty ? -1 : s.last! s.append(i) } var res = 1 var tuples = [(num: Int, index: Int)]() for i in 0..<n { tuples.append((nums[i], i)) } tuples.sort { a, b in a.num > b.num } for (num, i) in tuples { let operations = min( (i - prevGreaterOrEqualElement[i]) * (nextGreaterElement[i] - i), k) res = (res * pow(num, operations, MOD)) % MOD k -= operations if k == 0 { return res } } return res } func pow(_ x: Int, _ n: Int, _ mod: Int) -> Int { var res = 1 var x = x var n = n while n > 0 { if n % 2 == 1 { res = (res * x) % mod } x = (x * x) % mod n /= 2 } return res } }

Source: Github

11
Начать дискуссию