{"id":7260,"date":"2020-08-16T00:11:07","date_gmt":"2020-08-16T07:11:07","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7260"},"modified":"2020-08-16T10:21:35","modified_gmt":"2020-08-16T17:21:35","slug":"leetcode-1553-minimum-number-of-days-to-eat-n-oranges","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1553-minimum-number-of-days-to-eat-n-oranges\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1553. Minimum Number of Days to Eat N Oranges"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-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 1553. Minimum Number of Days to Eat N Oranges - \u5237\u9898\u627e\u5de5\u4f5c EP350\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/s66-UqMDoAo?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>There are&nbsp;<code>n<\/code>&nbsp;oranges in the kitchen and you decided to eat some of these oranges every day as follows:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Eat one orange.<\/li><li>If the number of remaining oranges (<code>n<\/code>) is divisible by 2 then you can eat&nbsp; n\/2 oranges.<\/li><li>If the number of remaining oranges (<code>n<\/code>) is divisible by 3&nbsp;then you can eat&nbsp; 2*(n\/3)&nbsp;oranges.<\/li><\/ul>\n\n\n\n<p>You can only choose one of the actions per day.<\/p>\n\n\n\n<p>Return the minimum number of days to eat&nbsp;<code>n<\/code>&nbsp;oranges.<\/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> n = 10\n<strong>Output:<\/strong> 4\n<strong>Explanation:<\/strong> You have 10 oranges.\nDay 1: Eat 1 orange,  10 - 1 = 9.  \nDay 2: Eat 6 oranges, 9 - 2*(9\/3) = 9 - 6 = 3. (Since 9 is divisible by 3)\nDay 3: Eat 2 oranges, 3 - 2*(3\/3) = 3 - 2 = 1. \nDay 4: Eat the last orange  1 - 1  = 0.\nYou need at least 4 days to eat the 10 oranges.\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> n = 6\n<strong>Output:<\/strong> 3\n<strong>Explanation:<\/strong> You have 6 oranges.\nDay 1: Eat 3 oranges, 6 - 6\/2 = 6 - 3 = 3. (Since 6 is divisible by 2).\nDay 2: Eat 2 oranges, 3 - 2*(3\/3) = 3 - 2 = 1. (Since 3 is divisible by 3)\nDay 3: Eat the last orange  1 - 1  = 0.\nYou need at least 3 days to eat the 6 oranges.\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> n = 1\n<strong>Output:<\/strong> 1\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> n = 56\n<strong>Output:<\/strong> 6\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= n &lt;= 2*10^9<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Greedy + DP<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/08\/1553-ep350-2.png\" alt=\"\" class=\"wp-image-7267\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/08\/1553-ep350-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/08\/1553-ep350-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/08\/1553-ep350-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/08\/1553-ep350-3.png\" alt=\"\" class=\"wp-image-7268\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/08\/1553-ep350-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/08\/1553-ep350-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/08\/1553-ep350-3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/08\/1553-ep350-4.png\" alt=\"\" class=\"wp-image-7269\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/08\/1553-ep350-4.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/08\/1553-ep350-4-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/08\/1553-ep350-4-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/08\/1553-ep350-5.png\" alt=\"\" class=\"wp-image-7270\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/08\/1553-ep350-5.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/08\/1553-ep350-5-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/08\/1553-ep350-5-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>Eat oranges one by one to make it a multiply of 2 or 3 such that we can eat 50% or 66.66&#8230;% of the oranges in one step.<br>dp(n) := min steps to finish n oranges.<br>base case n &lt;= 1, dp(n) = n<br>transition: dp(n) = 1 + min(n%2 + dp(n\/2), n % 3 + dp(n \/ 3))<br>e.g. n = 11, <br>we eat 11%2 = 1 in one step, left = 10 and then eat 10 \/ 2 = 5 in another step. 5 left for the subproblem.<br>we eat 11%3 = 2 in two steps, left = 9 and then eat 9 * 2 \/ 3 = 6 in another step, 3 left for the subproblem.<br>dp(11) = 1 + min(1 + dp(5), 2 + dp(3))<\/p>\n\n\n\n<p>T(n) = 2*T(n\/2) + O(1) = O(n)  <br>Time complexity: O(n) \/\/ w\/o memoization, close to O(logn) in practice.<br>Space complexity: O(logn)<\/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  int minDays(int n) {\n    unordered_map<int, int> cache;\n    function<int(int)> dp = [&](int n) {\n      if (n <= 1) return n;\n      auto it = cache.find(n);\n      if (it != cache.end()) return it->second;\n      return cache[n] = 1 + min(n % 2 + dp(n \/ 2), n % 3 + dp(n \/ 3));\n    };\n    return dp(n);\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"java\">\nclass Solution {\n  private static Map<Integer, Integer> cache = new HashMap<>();\n  public int minDays(int n) {\n    return dp(n);\n  }\n  \n  private int dp(int n) {\n    if (n <= 1) return n;\n    if (cache.containsKey(n)) return cache.get(n);    \n    int ans = 1 + Math.min(n % 2 + dp(n \/ 2), n % 3 + dp(n \/ 3));\n    cache.put(n, ans);\n    return ans;\n  }\n}\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python3\">\nclass Solution:\n  def minDays(self, n: int) -> int:\n    @lru_cache(None)\n    def dp(n):\n      if n <= 1: return n\n      return 1 + min(n % 2 + dp(n \/\/ 2), n % 3 + dp(n \/\/ 3))\n    return dp(n)\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: BFS<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/08\/1553-ep350-1.png\" alt=\"\" class=\"wp-image-7266\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/08\/1553-ep350-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/08\/1553-ep350-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/08\/1553-ep350-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>if x % 2 == 0, push x\/2 onto the queue<br>if x % 3 == 0, push x\/3 onto the queue<br>always push x - 1 onto the queue<\/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  int minDays(int n) {    \n    queue<int> q{{n}};\n    unordered_set<int> seen;\n    int steps = 0;\n    while (!q.empty()) {\n      int size = q.size();\n      while (size--) {\n        int x = q.front(); q.pop();        \n        if (x == 0) return steps;\n        if (x % 2 == 0 && seen.insert(x \/ 2).second)\n          q.push(x \/ 2);                  \n        if (x % 3 == 0 && seen.insert(x \/ 3).second)\n          q.push(x \/ 3);        \n        if (seen.insert(x - 1).second)\n          q.push(x - 1);        \n      }\n      ++steps;\n    }\n    return -1;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>There are&nbsp;n&nbsp;oranges in the kitchen and you decided to eat some of these oranges every day as follows: Eat one orange. If the number of&#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":[18,88,217],"class_list":["post-7260","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-greedy","tag-hard","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7260","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=7260"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7260\/revisions"}],"predecessor-version":[{"id":7271,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7260\/revisions\/7271"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7260"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7260"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7260"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}