C++ Prefix Product Solution Explained
Runtime: 224 ms, faster than 97.30% of C++ online submissions for Product of the Last K Numbers.\nMemory Usage: 70.5 MB, less than 5.76% of C++ online submissio
Runtime: 224 ms, faster than 97.30% of C++ online submissions for Product of the Last K Numbers.\nMemory Usage: 70.5 MB, less than 5.76% of C++ online submissions for Product of the Last K Numbers.\n\n```\nInorder to compute product of last k numbers we can store the prefix product of numbers in \nvector when a new number is added. Then the product of last k numbers can be found as:\n\nproduct of last k numbers = prefix_product[end] / prefix_product[end-k]\n\nend = last index of prefix product array \n\nExample: \n\nNumber Array: [1, 2, 3, 4, 5]\nPrefix Product: [1, 1, 2, 6, 24, 120] (Add 1 at first so that we can compute product for k == number array size)\n\nprefix_product_array->end = 5 (0 indexed)\n\nk = 1 => prefix_product[5] / prefix_product[4] = 120/24 = 5\nk = 2 => prefix_product[5] / prefix_product[3] = 120/6 = 20\nk = 3 => prefix_product[5] / prefix_product[2] = 120/2 = 60\nk = 4 => prefix_product[5] / prefix_product[1] = 120/1 = 120\nk = 5 => prefix_product[5] / prefix_product[0] = 120/1 = 120\n\nNow given array can contain zero in it and so we track the position of last zero and return\n0 if it last zero position is in the range of end-k-1 to end inclusive. Number array containing \nzero will have prefix product array as bellow,\n\nNumber Array: [1, 2, 0, 4, 5]\nPrefix Product: [1, 1, 2, 0, 4, 20]   (Add 1 at first)\n\nk = 1 => prefix_product[5] / prefix_product[4] = 20/4 = 5  (no zero)\nk = 2 => prefix_product[3] == 0 => prefix_product[5] = 20  (end-k is zero)\nk = 3 => prefix_product[3] == 0 => product = 0  (zero in last k numbers)\nk = 4 => prefix_product[3] == 0 => product = 0  (zero in last k numbers)\nk = 5 => prefix_product[3] == 0 => product = 0  (zero in last k numbers)\n\n```\n\n```\nclass ProductOfNumbers {\npublic:\n    \n    // store prefix product of numbers\n    vector<int>products;\n    \n    // store position of last zero number\n    int last_zero;\n    \n    ProductOfNumbers() {\n        \n        // insert initial value product value 1\n        products.push_back(1);\n        \n        // initially no zero value\n        last_zero  = -1;\n    }\n    \n    void add(int num) {\n        \n        // insert number if num == 0 or last number was 0 \n        if(num==0 || products.back()==0)\n        {\n            // update last zero position\n            if(num==0) last_zero = products.size();\n            \n            products.push_back(num);\n        }\n        else\n        {\n            // insert prefix product of current number  = last product * current number\n            products.push_back(products.back()*num);\n        }\n    }\n    \n    int getProduct(int k) {\n        \n        // position of the k th product from last\n        int limit = products.size()-k;\n        \n        // product will be zero if there is a zero in last k numbers\n        if(last_zero>=limit) return 0;\n        \n        // product will be prefix product[end] if prefix product[end-k] ==0 to avoid divide by zero\n        if(products[limit-1]==0) return products.back();\n        \n        // return prefix product[end] / prefix product[end-k]\n        return products.back()/products[limit-1];\n    }\n};\n```
['Design', 'C']