{"id":8173,"date":"2021-02-27T22:07:28","date_gmt":"2021-02-28T06:07:28","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8173"},"modified":"2021-03-04T19:20:27","modified_gmt":"2021-03-05T03:20:27","slug":"leetcode-1775-equal-sum-arrays-with-minimum-number-of-operations","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-1775-equal-sum-arrays-with-minimum-number-of-operations\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1775. Equal Sum Arrays With Minimum Number of Operations"},"content":{"rendered":"\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1775. Equal Sum Arrays With Minimum Number of Operations - \u5237\u9898\u627e\u5de5\u4f5c EP387\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/FdM_IFKXaHY?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>You are given two arrays of integers&nbsp;<code>nums1<\/code>&nbsp;and&nbsp;<code>nums2<\/code>, possibly of different lengths. The values in the arrays are between&nbsp;<code>1<\/code>&nbsp;and&nbsp;<code>6<\/code>, inclusive.<\/p>\n\n\n\n<p>In one operation, you can change any integer&#8217;s value in&nbsp;<strong>any&nbsp;<\/strong>of the arrays to&nbsp;<strong>any<\/strong>&nbsp;value between&nbsp;<code>1<\/code>&nbsp;and&nbsp;<code>6<\/code>, inclusive.<\/p>\n\n\n\n<p>Return&nbsp;<em>the minimum number of operations required to make the sum of values in&nbsp;<\/em><code>nums1<\/code><em>&nbsp;equal to the sum of values in&nbsp;<\/em><code>nums2<\/code><em>.<\/em>&nbsp;Return&nbsp;<code>-1<\/code>\u200b\u200b\u200b\u200b\u200b if it is not possible to make the sum of the two arrays equal.<\/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> nums1 = [1,2,3,4,5,6], nums2 = [1,1,2,2,2,2]\n<strong>Output:<\/strong> 3\n<strong>Explanation:<\/strong> You can make the sums of nums1 and nums2 equal with 3 operations. All indices are 0-indexed.\n- Change nums2[0] to 6. nums1 = [1,2,3,4,5,6], nums2 = [<strong>6<\/strong>,1,2,2,2,2].\n- Change nums1[5] to 1. nums1 = [1,2,3,4,5,<strong><u>1<\/u><\/strong>], nums2 = [6,1,2,2,2,2].\n- Change nums1[2] to 2. nums1 = [1,2,<strong><u>2<\/u><\/strong>,4,5,1], nums2 = [6,1,2,2,2,2].\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> nums1 = [1,1,1,1,1,1,1], nums2 = [6]\n<strong>Output:<\/strong> -1\n<strong>Explanation:<\/strong> There is no way to decrease the sum of nums1 or to increase the sum of nums2 to make them equal.\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> nums1 = [6,6], nums2 = [1]\n<strong>Output:<\/strong> 3\n<strong>Explanation:<\/strong> You can make the sums of nums1 and nums2 equal with 3 operations. All indices are 0-indexed. \n- Change nums1[0] to 2. nums1 = [<strong><u>2<\/u><\/strong>,6], nums2 = [1].\n- Change nums1[1] to 2. nums1 = [2,<strong><u>2<\/u><\/strong>], nums2 = [1].\n- Change nums2[0] to 4. nums1 = [2,2], nums2 = [<strong><u>4<\/u><\/strong>].\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= nums1.length, nums2.length &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>1 &lt;= nums1[i], nums2[i] &lt;= 6<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Greedy<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><a href=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1775-ep387-1.png\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1775-ep387-1.png\" alt=\"\" class=\"wp-image-8187\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1775-ep387-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1775-ep387-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1775-ep387-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><a href=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1775-ep387-2.png\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1775-ep387-2.png\" alt=\"\" class=\"wp-image-8188\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1775-ep387-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1775-ep387-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1775-ep387-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><a href=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1775-ep387-3.png\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1775-ep387-3.png\" alt=\"\" class=\"wp-image-8189\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1775-ep387-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1775-ep387-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1775-ep387-3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/figure>\n\n\n\n<p>Assuming sum(nums1) &lt; sum(nums2),<br>sort both arrays<br>* scan nums1 from left to right, we need to increase the value form the smallest one.<br>* scan nums2 from right to left, we need to decrease the value from the largest one.<br>Each time, select the one with the largest delta to change.<\/p>\n\n\n\n<p>e.g. nums1[i] = 2, nums[j] = 4, delta1 = 6 &#8211; 2 = 4, delta2 = 4 &#8211; 1 = 3, Increase 2 to 6 instead of decreasing 4 to 1.<\/p>\n\n\n\n<p>Time complexity: O(mlogm + nlogn)<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 minOperations(vector<int>& nums1, vector<int>& nums2) {\n    const int l1 = nums1.size();\n    const int l2 = nums2.size();\n    if (min(l1, l2) * 6 < max(l1, l2)) return -1;\n    int s1 = accumulate(begin(nums1), end(nums1), 0);\n    int s2 = accumulate(begin(nums2), end(nums2), 0);\n    if (s1 > s2) return minOperations(nums2, nums1);\n    sort(begin(nums1), end(nums1));\n    sort(begin(nums2), end(nums2));\n    int ans = 0;    \n    int i = 0;\n    int j = l2 - 1;\n    while (s1 != s2) {      \n      const int diff = s2 - s1;      \n      if (j == l2 || (i != l1 && 6 - nums1[i] >= nums2[j] - 1)) {\n        const int x = min(6, nums1[i] + diff);\n        s1 += x - nums1[i++];        \n      } else {\n        const int x = max(1, nums2[j] - diff);\n        s2 += x - nums2[j--];      \n      }\n      ++ans;\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given two arrays of integers&nbsp;nums1&nbsp;and&nbsp;nums2, possibly of different lengths. The values in the arrays are between&nbsp;1&nbsp;and&nbsp;6, inclusive. In one operation, you can change&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[51],"tags":[88,177],"class_list":["post-8173","post","type-post","status-publish","format-standard","hentry","category-greedy","tag-greedy","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8173","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=8173"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8173\/revisions"}],"predecessor-version":[{"id":8190,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8173\/revisions\/8190"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8173"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8173"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8173"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}