{"id":9214,"date":"2021-12-24T00:15:09","date_gmt":"2021-12-24T08:15:09","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9214"},"modified":"2021-12-24T00:16:12","modified_gmt":"2021-12-24T08:16:12","slug":"leetcode-1300-sum-of-mutated-array-closest-to-target","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/binary-search\/leetcode-1300-sum-of-mutated-array-closest-to-target\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1300. Sum of Mutated Array Closest to Target"},"content":{"rendered":"\n<p>Given an integer array&nbsp;<code>arr<\/code>&nbsp;and a target value&nbsp;<code>target<\/code>, return the integer&nbsp;<code>value<\/code>&nbsp;such that when we change all the integers larger than&nbsp;<code>value<\/code>&nbsp;in the given array to be equal to&nbsp;<code>value<\/code>, the sum of the array gets as close as possible (in absolute difference) to&nbsp;<code>target<\/code>.<\/p>\n\n\n\n<p>In case of a tie, return the minimum such integer.<\/p>\n\n\n\n<p>Notice that the answer is not neccesarilly a number from&nbsp;<code>arr<\/code>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> arr = [4,9,3], target = 10\n<strong>Output:<\/strong> 3\n<strong>Explanation:<\/strong> When using 3 arr converts to [3, 3, 3] which sums 9 and that's the optimal answer.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> arr = [2,3,5], target = 10\n<strong>Output:<\/strong> 5\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> arr = [60864,25176,27249,21296,20204], target = 56803\n<strong>Output:<\/strong> 11361\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= arr.length &lt;= 10<sup>4<\/sup><\/code><\/li><li><code>1 &lt;= arr[i], target &lt;= 10<sup>5<\/sup><\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Binary Search<\/strong><\/h2>\n\n\n\n<p>Find the smallest number x s.t. sum of the mutated array is >= target. Answer must be either x or x &#8211; 1.<\/p>\n\n\n\n<p>Note, the search range should be [0, max(arr))<\/p>\n\n\n\n<p>Time complexity: O(nlogm)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua]\nclass Solution {\npublic:\n  int findBestValue(vector<int>& arr, int target) {\n    int l = 0;\n    int r = *max_element(begin(arr), end(arr));\n    int ans = 0;\n    auto sum = [&](int v) {\n      int ans = 0;\n      for (int x : arr)\n        ans += min(x, v);\n      return ans;\n    };\n    while (l < r) {\n      int m = l + (r - l) \/ 2;            \n      if (sum(m) >= target)\n        r = m;\n      else\n        l = m + 1;\n    }\n    return abs(sum(l) - target) < abs(sum(l - 1) - target) ? l : l - 1;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given an integer array&nbsp;arr&nbsp;and a target value&nbsp;target, return the integer&nbsp;value&nbsp;such that when we change all the integers larger than&nbsp;value&nbsp;in the given array to be equal&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[149],"tags":[52,177],"class_list":["post-9214","post","type-post","status-publish","format-standard","hentry","category-binary-search","tag-binary-search","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9214","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=9214"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9214\/revisions"}],"predecessor-version":[{"id":9218,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9214\/revisions\/9218"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9214"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9214"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9214"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}