{"id":352631,"date":"2024-05-20T22:12:20","date_gmt":"2024-05-20T22:12:20","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=352631"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=352631","title":{"rendered":"<span>LeetCode, Hard: 2818. Apply Operations to Maximize Score. Swift<\/span>"},"content":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<h3>Description<\/h3>\n<p>You are given an array nums of n positive integers and an integer k.<\/p>\n<p>Initially, you start with a score of 1. You have to maximize your score by applying the following operation at most k times:<\/p>\n<ul>\n<li>\n<p>Choose any non-empty subarray nums[l, &#8230;, r] that you haven&#8217;t chosen previously.<\/p>\n<\/li>\n<li>\n<p>Choose an element x of nums[l, &#8230;, r] with the highest prime score. If multiple such elements exist, choose the one with the smallest index.<\/p>\n<\/li>\n<li>\n<p>Multiply your score by x.<\/p>\n<\/li>\n<\/ul>\n<p>Here,\u00a0<code>nums[l, ..., r]<\/code>\u00a0denotes the subarray of\u00a0<code>nums<\/code>\u00a0starting at index\u00a0<code>l<\/code>\u00a0and ending at the index\u00a0<code>r<\/code>, both ends being inclusive.<\/p>\n<p>The prime score of an integer\u00a0<code>x<\/code>\u00a0is equal to the number of distinct prime factors of\u00a0<code>x<\/code>. For example, the prime score of\u00a0<code>300<\/code>\u00a0is\u00a0<code>3<\/code>\u00a0since\u00a0<code>300 = 2 * 2 * 3 * 5 * 5<\/code>.<\/p>\n<p><strong>Return<\/strong>\u00a0the maximum possible score after applying at most\u00a0<code>k<\/code>\u00a0operations.<\/p>\n<p>Since the answer may be large, return it modulo\u00a0<code>10^9 + 7<\/code>.<\/p>\n<p>Example 1:<\/p>\n<pre><code>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.<\/code><\/pre>\n<p>Example 2:<\/p>\n<pre><code>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.<\/code><\/pre>\n<p>Constraints:<br \/>1 &lt;= nums.length == n &lt;= 10^5<br \/>1 &lt;= nums[i] &lt;= 10^5<br \/>1 &lt;= k &lt;= min(n * (n + 1) \/ 2, 10^9)<\/p>\n<h3>Approach<\/h3>\n<p>1 Compute Prime Scores:<\/p>\n<ul>\n<li>\n<p>Calculate the prime score for each integer in the array nums. Prime score represents the number of distinct prime factors of an integer.<\/p>\n<\/li>\n<li>\n<p>Initialize a boolean array prime of size upper, where upper is the maximum element in nums plus 1.<\/p>\n<\/li>\n<li>\n<p>Initialize an integer array primeScore of the same size.<\/p>\n<\/li>\n<li>\n<p>Set prime[0] and prime[1] to false.<\/p>\n<\/li>\n<li>\n<p>Iterate over integers from 2 to upper &#8212; 1, and update primeScore and prime based on their prime factors.<\/p>\n<\/li>\n<\/ul>\n<p>2 Compute Next Greater Elements:<\/p>\n<ul>\n<li>\n<p>Initialize arrays nextGreaterElement and prevGreaterOrEqualElement of size n, where n is the length of nums.<\/p>\n<\/li>\n<li>\n<p>Use a monotonic stack to find the next greater element with a greater prime score for each element in nums.<\/p>\n<\/li>\n<li>\n<p>Iterate through nums and maintain a stack of indices.<\/p>\n<\/li>\n<li>\n<p>For each element, pop elements from the stack if their prime score is less than or equal to the current element&#8217;s prime score.<\/p>\n<\/li>\n<li>\n<p>Record the index of the top of the stack as the nextGreaterElement if the stack is not empty, else set it to n.<\/p>\n<\/li>\n<li>\n<p>Repeat the above process in reverse to compute prevGreaterOrEqualElement.<\/p>\n<\/li>\n<\/ul>\n<p>3 Sort and Process Elements:<\/p>\n<ul>\n<li>\n<p>Create an array of tuples (num, i) where num is the value of an element and i is its index in nums.<\/p>\n<\/li>\n<li>\n<p>Sort the tuples in descending order of the first element (num).<\/p>\n<\/li>\n<li>\n<p>Loop through the sorted tuples and perform the following steps:<\/p>\n<ul>\n<li>\n<p>Compute the number of operations as the minimum of (i &#8212; prevGreaterOrEqualElement[i]) * (nextGreaterElement[i] &#8212; i) and k.<\/p>\n<\/li>\n<li>\n<p>Update res by multiplying it with pow(num, operations) modulo MOD using the helper function pow.<\/p>\n<\/li>\n<li>\n<p>Decrement k by the number of operations.<\/p>\n<\/li>\n<li>\n<p>If k becomes 0, return res.<\/p>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>4 Helper Function for Exponentiation:<\/p>\n<ul>\n<li>\n<p>Implement the pow function to calculate exponentiation efficiently using modular arithmetic.<\/p>\n<\/li>\n<\/ul>\n<h3>Complexity<\/h3>\n<ul>\n<li>\n<p><strong>Time complexity<\/strong>:\u00a0<code>O(max(nums) * log(max(nums)) + n * log(n))<\/code>. Accounting for computing prime scores, using the stack to compute next greater elements, and sorting the tuples.<\/p>\n<\/li>\n<li>\n<p><strong>Space complexity<\/strong>:\u00a0<code>O(max(nums) + n)<\/code>. Considering the space required for arrays and the stack used for computation.<\/p>\n<\/li>\n<\/ul>\n<h3>Code (Swift)<\/h3>\n<pre><code class=\"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..&lt;upper {             if prime[i] {                 var j = i                 while j &lt; upper {                     primeScore[j] += 1                     prime[j] = false                     j += i                 }             }         }          var nextGreaterElement = [Int](repeating: n, count: n)         var s = [Int]()         for i in (0..&lt;n).reversed() {             while !s.isEmpty &amp;&amp; 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..&lt;n {             while !s.isEmpty &amp;&amp; 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..&lt;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     } }<\/code><\/pre>\n<p>Source:\u00a0<a href=\"https:\/\/github.com\/sergeyleschev\/leetcode-swift\/blob\/main\/2501-3000\/2818.%20Apply%20Operations%20to%20Maximize%20Score.swift\" rel=\"noopener noreferrer nofollow\"><u>Github<\/u><\/a><\/p>\n<\/p>\n<\/div>\n<\/div>\n<\/div>\n<p><!----><!----><\/div>\n<p><!----><!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/articles\/755656\/\"> https:\/\/habr.com\/ru\/articles\/755656\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<h3>Description<\/h3>\n<p>You are given an array nums of n positive integers and an integer k.<\/p>\n<p>Initially, you start with a score of 1. You have to maximize your score by applying the following operation at most k times:<\/p>\n<ul>\n<li>\n<p>Choose any non-empty subarray nums[l, &#8230;, r] that you haven&#8217;t chosen previously.<\/p>\n<\/li>\n<li>\n<p>Choose an element x of nums[l, &#8230;, r] with the highest prime score. If multiple such elements exist, choose the one with the smallest index.<\/p>\n<\/li>\n<li>\n<p>Multiply your score by x.<\/p>\n<\/li>\n<\/ul>\n<p>Here,\u00a0<code>nums[l, ..., r]<\/code>\u00a0denotes the subarray of\u00a0<code>nums<\/code>\u00a0starting at index\u00a0<code>l<\/code>\u00a0and ending at the index\u00a0<code>r<\/code>, both ends being inclusive.<\/p>\n<p>The prime score of an integer\u00a0<code>x<\/code>\u00a0is equal to the number of distinct prime factors of\u00a0<code>x<\/code>. For example, the prime score of\u00a0<code>300<\/code>\u00a0is\u00a0<code>3<\/code>\u00a0since\u00a0<code>300 = 2 * 2 * 3 * 5 * 5<\/code>.<\/p>\n<p><strong>Return<\/strong>\u00a0the maximum possible score after applying at most\u00a0<code>k<\/code>\u00a0operations.<\/p>\n<p>Since the answer may be large, return it modulo\u00a0<code>10^9 + 7<\/code>.<\/p>\n<p>Example 1:<\/p>\n<pre><code>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.<\/code><\/pre>\n<p>Example 2:<\/p>\n<pre><code>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.<\/code><\/pre>\n<p>Constraints:<br \/>1 &lt;= nums.length == n &lt;= 10^5<br \/>1 &lt;= nums[i] &lt;= 10^5<br \/>1 &lt;= k &lt;= min(n * (n + 1) \/ 2, 10^9)<\/p>\n<h3>Approach<\/h3>\n<p>1 Compute Prime Scores:<\/p>\n<ul>\n<li>\n<p>Calculate the prime score for each integer in the array nums. Prime score represents the number of distinct prime factors of an integer.<\/p>\n<\/li>\n<li>\n<p>Initialize a boolean array prime of size upper, where upper is the maximum element in nums plus 1.<\/p>\n<\/li>\n<li>\n<p>Initialize an integer array primeScore of the same size.<\/p>\n<\/li>\n<li>\n<p>Set prime[0] and prime[1] to false.<\/p>\n<\/li>\n<li>\n<p>Iterate over integers from 2 to upper &#8212; 1, and update primeScore and prime based on their prime factors.<\/p>\n<\/li>\n<\/ul>\n<p>2 Compute Next Greater Elements:<\/p>\n<ul>\n<li>\n<p>Initialize arrays nextGreaterElement and prevGreaterOrEqualElement of size n, where n is the length of nums.<\/p>\n<\/li>\n<li>\n<p>Use a monotonic stack to find the next greater element with a greater prime score for each element in nums.<\/p>\n<\/li>\n<li>\n<p>Iterate through nums and maintain a stack of indices.<\/p>\n<\/li>\n<li>\n<p>For each element, pop elements from the stack if their prime score is less than or equal to the current element&#8217;s prime score.<\/p>\n<\/li>\n<li>\n<p>Record the index of the top of the stack as the nextGreaterElement if the stack is not empty, else set it to n.<\/p>\n<\/li>\n<li>\n<p>Repeat the above process in reverse to compute prevGreaterOrEqualElement.<\/p>\n<\/li>\n<\/ul>\n<p>3 Sort and Process Elements:<\/p>\n<ul>\n<li>\n<p>Create an array of tuples (num, i) where num is the value of an element and i is its index in nums.<\/p>\n<\/li>\n<li>\n<p>Sort the tuples in descending order of the first element (num).<\/p>\n<\/li>\n<li>\n<p>Loop through the sorted tuples and perform the following steps:<\/p>\n<ul>\n<li>\n<p>Compute the number of operations as the minimum of (i &#8212; prevGreaterOrEqualElement[i]) * (nextGreaterElement[i] &#8212; i) and k.<\/p>\n<\/li>\n<li>\n<p>Update res by multiplying it with pow(num, operations) modulo MOD using the helper function pow.<\/p>\n<\/li>\n<li>\n<p>Decrement k by the number of operations.<\/p>\n<\/li>\n<li>\n<p>If k becomes 0, return res.<\/p>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>4 Helper Function for Exponentiation:<\/p>\n<ul>\n<li>\n<p>Implement the pow function to calculate exponentiation efficiently using modular arithmetic.<\/p>\n<\/li>\n<\/ul>\n<h3>Complexity<\/h3>\n<ul>\n<li>\n<p><strong>Time complexity<\/strong>:\u00a0<code>O(max(nums) * log(max(nums)) + n * log(n))<\/code>. Accounting for computing prime scores, using the stack to compute next greater elements, and sorting the tuples.<\/p>\n<\/li>\n<li>\n<p><strong>Space complexity<\/strong>:\u00a0<code>O(max(nums) + n)<\/code>. Considering the space required for arrays and the stack used for computation.<\/p>\n<\/li>\n<\/ul>\n<h3>Code (Swift)<\/h3>\n<pre><code class=\"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..&lt;upper {             if prime[i] {                 var j = i                 while j &lt; upper {                     primeScore[j] += 1                     prime[j] = false                     j += i                 }             }         }          var nextGreaterElement = [Int](repeating: n, count: n)         var s = [Int]()         for i in (0..&lt;n).reversed() {             while !s.isEmpty &amp;&amp; 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..&lt;n {             while !s.isEmpty &amp;&amp; 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..&lt;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     } }<\/code><\/pre>\n<p>Source:\u00a0<a href=\"https:\/\/github.com\/sergeyleschev\/leetcode-swift\/blob\/main\/2501-3000\/2818.%20Apply%20Operations%20to%20Maximize%20Score.swift\" rel=\"noopener noreferrer nofollow\"><u>Github<\/u><\/a><\/p>\n<\/p>\n<\/div>\n<\/div>\n<\/div>\n<p><!----><!----><\/div>\n<p><!----><!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/articles\/755656\/\"> https:\/\/habr.com\/ru\/articles\/755656\/<\/a><br \/><\/br><\/br><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-352631","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/352631","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=352631"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/352631\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=352631"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=352631"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=352631"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}