{"id":6330,"date":"2020-02-16T10:00:40","date_gmt":"2020-02-16T18:00:40","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6330"},"modified":"2020-02-16T10:02:48","modified_gmt":"2020-02-16T18:02:48","slug":"leetcode-1352-product-of-the-last-k-numbers","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-1352-product-of-the-last-k-numbers\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1352. Product of the Last K Numbers"},"content":{"rendered":"\n<p>Implement the class&nbsp;<code>ProductOfNumbers<\/code>&nbsp;that supports two methods:<\/p>\n\n\n\n<p>1.<code>&nbsp;add(int num)<\/code><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Adds the number&nbsp;<code>num<\/code>&nbsp;to the back of the current list of numbers.<\/li><\/ul>\n\n\n\n<p>2.<code>&nbsp;getProduct(int k)<\/code><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Returns the product of the last&nbsp;<code>k<\/code>&nbsp;numbers in the current list.<\/li><li>You can assume that always the current list has&nbsp;<strong>at least<\/strong>&nbsp;<code>k<\/code>&nbsp;numbers.<\/li><\/ul>\n\n\n\n<p>At any time, the product of any contiguous sequence of numbers will fit into a single 32-bit integer without overflowing.<\/p>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input<\/strong>\n[\"ProductOfNumbers\",\"add\",\"add\",\"add\",\"add\",\"add\",\"getProduct\",\"getProduct\",\"getProduct\",\"add\",\"getProduct\"]\n[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]\n\n<strong>Output:<\/strong> [null,null,null,null,null,null,20,40,0,null,32]\n<strong>Explanation:<\/strong>\nProductOfNumbers productOfNumbers = new ProductOfNumbers();\nproductOfNumbers.add(3);        \/\/ [3] \nproductOfNumbers.add(0);        \/\/ [3,0] \nproductOfNumbers.add(2);        \/\/ [3,0,2]\nproductOfNumbers.add(5);        \/\/ [3,0,2,5]\nproductOfNumbers.add(4);        \/\/ [3,0,2,5,4]\nproductOfNumbers.getProduct(2); \/\/ return 20.\nThe product of the last 2 numbers is 5 * 4 = 20\nproductOfNumbers.getProduct(3); \/\/ return 40. The product of the last 3 numbers is 2 * 5 * 4 = 40 \nproductOfNumbers.getProduct(4); \/\/ return 0. The product of the last 4 numbers is 0 * 2 * 5 * 4 = 0\nproductOfNumbers.add(8);        \/\/ [3,0,2,5,4,8]\nproductOfNumbers.getProduct(2); \/\/ return 32. The product of the last 2 numbers is 4 * 8 = 32  \n<\/pre>\n\n\n\n<p><\/p>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>There will be at most&nbsp;<code>40000<\/code>&nbsp;operations considering both&nbsp;<code>add<\/code>&nbsp;and&nbsp;<code>getProduct<\/code>.<\/li><li><code>0 &lt;= num&nbsp;&lt;=&nbsp;100<\/code><\/li><li><code>1 &lt;= k &lt;= 40000<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Prefix product<\/strong><\/h2>\n\n\n\n<p>Use p[i] to store the prod of a1*a2*&#8230;ai<br>p[i] = ai*p[i-1]<br>If ai is 0, reset p = [1].<br>Compare k with the len(p), if k is greater than len(p) which means there is 0 recently, return 0.<br>otherwise return p[n] \/ p[n &#8211; k &#8211; 1]<\/p>\n\n\n\n<p>Time complexity: Add: O(1), getProduct: O(1)<br>Space complexity: O(n)<\/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 ProductOfNumbers {\npublic:\n  ProductOfNumbers(): p_(1, 1) { }\n\n  void add(int num) {\n    if (num == 0) {\n      p_.clear();\n      p_.push_back(1);\n    } else {\n      p_.push_back(p_.back() * num);\n    }\n  }\n\n  int getProduct(int k) {\n    if (k >= p_.size()) return 0;\n    \/\/ a_1*a_2*...*a_n \/ a_1*a_2*...*a_n-k-1.\n    return p_.back() \/ p_[p_.size() - k - 1];\n  }\nprivate:\n  vector<int> p_;\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Implement the class&nbsp;ProductOfNumbers&nbsp;that supports two methods: 1.&nbsp;add(int num) Adds the number&nbsp;num&nbsp;to the back of the current list of numbers. 2.&nbsp;getProduct(int k) Returns the product 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":[184],"tags":[177,97],"class_list":["post-6330","post","type-post","status-publish","format-standard","hentry","category-array","tag-medium","tag-prefix","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6330","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=6330"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6330\/revisions"}],"predecessor-version":[{"id":6332,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6330\/revisions\/6332"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6330"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6330"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6330"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}