✔️ [C++] PREFIXES (🌸◠‿◠), Explained
UPVOTE if you like (\uD83C\uDF38\u25E0\u203F\u25E0), If you have any question, feel free to ask.\n\nHow can we make getProduct with constant time complexity? On
**UPVOTE if you like (\uD83C\uDF38\u25E0\u203F\u25E0), If you have any question, feel free to ask.**\n\nHow can we make `getProduct` with constant time complexity? On every `add` we can do some precalculations. We can create an array of prefixes where `i`th element represents a product of all elements starting from the very first element up to the `i`th one. But how will it help us to calculate the product for the last `k` elements? We just need to chisel away the superfluous material. We take the very last prefix and divide it by the prefix at the index `size - k`. Another problem we have to account for is how to deal with zeros. If any zero comes from the stream, all prefixes after just turn to zero. We can simply clear the prefix array since everything before zero anyway become zero and we don\'t care about them.\n\nTime: O(1) - for getting product\nSpace: O(n) - for prefixes\n\nRuntime: 128 ms, faster than **99.03%** of C++ online submissions for Product of the Last K Numbers.\nMemory Usage: 70 MB, less than **71.69%** of C++ online submissions for Product of the Last K Numbers.\n\n```\nclass ProductOfNumbers {\nprivate:\n    vector<int> prefix = {1};\npublic:\n    ProductOfNumbers() {\n        \n    }\n    \n    void add(int num) {\n        if (num == 0)\n            prefix = {1};\n        else\n            prefix.push_back(prefix.back() * num);\n    }\n\n    int getProduct(int k) {\n        int size = prefix.size() - 1;\n        if (k > size) return 0;\n        \n        return prefix.back()/prefix[size - k];\n    }\n};\n\n```\n\n**UPVOTE if you like (\uD83C\uDF38\u25E0\u203F\u25E0), If you have any question, feel free to ask.**\n\n
['C']