aboutsummaryrefslogtreecommitdiff
path: root/product_last_k_num.c
blob: a0ed930a0fb0b0fb93216aadf05b66f89148374b (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
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);
}