{"id":7655,"date":"2020-11-14T12:21:41","date_gmt":"2020-11-14T20:21:41","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7655"},"modified":"2020-11-14T16:45:48","modified_gmt":"2020-11-15T00:45:48","slug":"leetcode-1655-distribute-repeating-integers","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1655-distribute-repeating-integers\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1655. Distribute Repeating Integers"},"content":{"rendered":"\n<p>You are given an array of&nbsp;<code>n<\/code>&nbsp;integers,&nbsp;<code>nums<\/code>, where there are at most&nbsp;<code>50<\/code>&nbsp;unique values in the array. You are also given an array of&nbsp;<code>m<\/code>&nbsp;customer order quantities,&nbsp;<code>quantity<\/code>, where&nbsp;<code>quantity[i]<\/code>&nbsp;is the amount of integers the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;customer ordered. Determine if it is possible to distribute&nbsp;<code>nums<\/code>&nbsp;such that:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>The&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;customer gets&nbsp;<strong>exactly<\/strong>&nbsp;<code>quantity[i]<\/code>&nbsp;integers,<\/li><li>The integers the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;customer gets are&nbsp;<strong>all equal<\/strong>, and<\/li><li>Every customer is satisfied.<\/li><\/ul>\n\n\n\n<p>Return&nbsp;<code>true<\/code><em>&nbsp;if it is possible to distribute&nbsp;<\/em><code>nums<\/code><em>&nbsp;according to the above conditions<\/em>.<\/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> nums = [1,2,3,4], quantity = [2]\n<strong>Output:<\/strong> false\n<strong>Explanation:<\/strong> The 0th customer cannot be given two different integers.\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> nums = [1,2,3,3], quantity = [2]\n<strong>Output:<\/strong> true\n<strong>Explanation:<\/strong> The 0th customer is given [3,3]. The integers [1,2] are not used.\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> nums = [1,1,2,2], quantity = [2,2]\n<strong>Output:<\/strong> true\n<strong>Explanation:<\/strong> The 0th customer is given [1,1], and the 1st customer is given [2,2].\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [1,1,2,3], quantity = [2,2]\n<strong>Output:<\/strong> false\n<strong>Explanation:<\/strong> Although the 0th customer could be given [1,1], the 1st customer cannot be satisfied.<\/pre>\n\n\n\n<p><strong>Example 5:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [1,1,1,1,1], quantity = [2,3]\n<strong>Output:<\/strong> true\n<strong>Explanation:<\/strong> The 0th customer is given [1,1], and the 1st customer is given [1,1,1].\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>n == nums.length<\/code><\/li><li><code>1 &lt;= n &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>1 &lt;= nums[i] &lt;= 1000<\/code><\/li><li><code>m == quantity.length<\/code><\/li><li><code>1 &lt;= m &lt;= 10<\/code><\/li><li><code>1 &lt;= quantity[i] &lt;= 10<sup>5<\/sup><\/code><\/li><li>There are at most&nbsp;<code>50<\/code>&nbsp;unique values in&nbsp;<code>nums<\/code>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution1: Backtracking<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(|vals|^m) <br>Space complexity: O(|vals| + m)<\/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  bool canDistribute(vector<int>& nums, vector<int>& quantity) {\n    unordered_map<int, int> m;\n    for (int x : nums) ++m[x];\n    vector<int> cnt;\n    for (const auto& [x, c] : m) cnt.push_back(c);\n    \n    const int q = quantity.size();\n    const int n = cnt.size();\n    function<bool(int)> dfs = [&](int d) {\n      if (d == q) return true;\n      for (int i = 0; i < n; ++i) \n        if (cnt[i] >= quantity[d]) {\n          cnt[i] -= quantity[d];\n          if (dfs(d + 1)) return true;\n          cnt[i] += quantity[d];\n        }\n      return false;\n    };\n    \n    sort(rbegin(cnt), rend(cnt));\n    sort(rbegin(quantity), rend(quantity));\n    \n    return dfs(0);\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Bitmask + all subsets<\/strong><\/h2>\n\n\n\n<p>dp(mask, i) := whether we can distribute to a subset of customers represented as a bit mask, using the i-th to (n-1)-th numbers.<\/p>\n\n\n\n<p>Time complexity: O(2^m * m * |vals|) = O(2^10 * 10 * 50)<br>Space complexity: O(2^m * |vals|)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  bool canDistribute(vector<int>& nums, vector<int>& quantity) {\n    vector<int> cnt;\n    unordered_map<int, int> freq;\n    for (int x : nums) ++freq[x]; \n    for (const auto& [x, f] : freq) cnt.push_back(f);\n    \n    const int n = cnt.size();\n    const int m = quantity.size();        \n    \n    vector<vector<optional<bool>>> cache(1 << m, vector<optional<bool>>(n));\n    \n    vector<int> sums(1 << m);\n    for (int mask = 0; mask < 1 << m; ++mask)\n      for (int i = 0; i < m; ++i)\n        if (mask &#038; (1 << i))\n          sums[mask] += quantity[i];\n    \n    function<bool(int, int)> dp = [&](int mask, int i) -> bool {\n      if (mask == 0) return true;\n      if (i == n) return false;\n      \n      auto& ans = cache[mask][i];\n      \n      if (ans.has_value()) return ans.value();\n      \n      int cur = mask;\n      while (cur) {\n        if (sums[cur] <= cnt[i] &#038;&#038; dp(mask ^ cur, i + 1)) {\n          ans = true;\n          return true;\n        }\n        cur = (cur - 1) &#038; mask;\n      }\n      \n      ans = dp(mask, i + 1);\n      return ans.value();\n    };\n    \n    return dp((1 << m) - 1, 0);\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\n# Author: Huahua\nclass Solution:\n  def canDistribute(self, nums: List[int], \n                    quantity: List[int]) -> bool:    \n    cnts = list(Counter(nums).values())\n    m = len(quantity)\n    n = len(cnts)\n    sums = [0] * (1 << m)\n    for mask in range(1 << m):\n      for i in range(m):\n        if mask &#038; (1 << i): sums[mask] += quantity[i]\n    \n    @lru_cache(None)\n    def dp(mask: int, i: int) -> bool:\n      if not mask: return True\n      if i < 0: return False\n      \n      cur = mask\n      while cur:\n        if sums[cur] <= cnts[i] and dp(mask ^ cur, i - 1):\n          return True\n        cur = (cur - 1) &#038; mask\n      \n      return dp(mask, i - 1)\n    \n    return dp((1 << m) - 1, n - 1)\n<\/pre>\n<\/div><\/div>\n\n\n\n<p>Bottom up:<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  bool canDistribute(vector<int>& nums, vector<int>& quantity) {\n    vector<int> cnt;\n    unordered_map<int, int> freq;\n    for (int x : nums) ++freq[x]; \n    for (const auto& [x, f] : freq) cnt.push_back(f);\n    \n    const int n = cnt.size();\n    const int m = quantity.size();            \n    \n    vector<int> sums(1 << m);\n    for (int mask = 0; mask < 1 << m; ++mask)\n      for (int i = 0; i < m; ++i)\n        if (mask &#038; (1 << i))\n          sums[mask] += quantity[i];\n    \n    \/\/ dp[mask][i] := use first i types to satisfy mask customers.\n    vector<vector<int>> dp(1 << m, vector<int>(n + 1));\n    dp[0][0] = 1;    \n    for (int mask = 0; mask < 1 << m; ++mask)\n      for (int i = 0; i < n; ++i) {\n        dp[mask][i + 1] |= dp[mask][i];\n        for (int cur = mask; cur; cur = (cur - 1) &#038; mask)\n          if (sums[cur] <= cnt[i] &#038;&#038; dp[mask ^ cur][i])\n            dp[mask][i + 1] = 1;\n      }\n    \n    return dp[(1 << m) - 1][n];\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>You are given an array of&nbsp;n&nbsp;integers,&nbsp;nums, where there are at most&nbsp;50&nbsp;unique values in the array. You are also given an array of&nbsp;m&nbsp;customer order quantities,&nbsp;quantity, where&nbsp;quantity[i]&nbsp;is&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[621,33,18,42],"class_list":["post-7655","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-bitmask","tag-dfs","tag-dp","tag-search","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7655","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=7655"}],"version-history":[{"count":7,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7655\/revisions"}],"predecessor-version":[{"id":7664,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7655\/revisions\/7664"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7655"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7655"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7655"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}