aboutsummaryrefslogtreecommitdiff
path: root/product_last_k_num.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-02-13 20:18:20 -0700
committerJack Sangdahl <[email protected]>2025-02-13 20:18:20 -0700
commit174c3b55b04c6a71e22712ce599afdece018ee39 (patch)
treecfeef243ad79c7b6288c4080602a5961962c6e78 /product_last_k_num.c
parentc925f1740cfe00cea69b6e091dcb38d114887ad3 (diff)
downloadleetcode-174c3b55b04c6a71e22712ce599afdece018ee39.tar.gz
leetcode-174c3b55b04c6a71e22712ce599afdece018ee39.zip
1352. product of the last k numbers
Diffstat (limited to 'product_last_k_num.c')
-rw-r--r--product_last_k_num.c67
1 files changed, 67 insertions, 0 deletions
diff --git a/product_last_k_num.c b/product_last_k_num.c
new file mode 100644
index 0000000..a0ed930
--- /dev/null
+++ b/product_last_k_num.c
@@ -0,0 +1,67 @@
+// 1352. Product of the Last K Numbers
+#include "leetcode.h"
+
+/*
+ * design an algorithm that accepts a stream of integers and retrieves the
+ * product of the last 'k' integers of the stream. implement the
+ * 'ProductOfNumbers' class. the test cases are generated so that at any time,
+ * the product of any contiguous sequence of numbers will fit into a single
+ * 32-bit integer without overflowing.
+ */
+
+typedef struct {
+ int *pre;
+ int size;
+ int capacity;
+} ProductOfNumbers;
+
+ProductOfNumbers *productOfNumbersCreate() {
+ ProductOfNumbers *obj =
+ (ProductOfNumbers *)calloc(1, sizeof(ProductOfNumbers));
+ obj->pre = (int *)calloc(2, sizeof(int));
+ obj->pre[0] = 1;
+ obj->size = 1;
+ obj->capacity = 2;
+ return obj;
+}
+
+void productOfNumbersAdd(ProductOfNumbers *obj, int num) {
+ if (obj->size == obj->capacity) {
+ obj->capacity *= 2;
+ obj->pre = (int *)realloc(obj->pre, obj->capacity * sizeof(int));
+ }
+ if (num) {
+ int prev = obj->pre[obj->size - 1];
+ obj->pre[obj->size++] = prev * num;
+ } else {
+ obj->size = 0;
+ obj->capacity = 2;
+ obj->pre = (int *)realloc(obj->pre, obj->capacity * sizeof(int));
+ obj->pre[obj->size++] = 1;
+ }
+}
+
+int productOfNumbersGetProduct(ProductOfNumbers *obj, int k) {
+ return k < obj->size ? obj->pre[obj->size - 1] / obj->pre[obj->size - k - 1]
+ : 0;
+}
+
+void productOfNumbersFree(ProductOfNumbers *obj) {
+ free(obj->pre);
+ free(obj);
+}
+
+int main() {
+ ProductOfNumbers *obj = productOfNumbersCreate();
+ productOfNumbersAdd(obj, 3);
+ productOfNumbersAdd(obj, 0);
+ productOfNumbersAdd(obj, 2);
+ productOfNumbersAdd(obj, 5);
+ productOfNumbersAdd(obj, 4);
+ printf("%d\n", productOfNumbersGetProduct(obj, 2)); // expect: 20
+ printf("%d\n", productOfNumbersGetProduct(obj, 3)); // expect: 40
+ printf("%d\n", productOfNumbersGetProduct(obj, 4)); // expect: 0
+ productOfNumbersAdd(obj, 8);
+ printf("%d\n", productOfNumbersGetProduct(obj, 2)); // expect: 32
+ productOfNumbersFree(obj);
+}