aboutsummaryrefslogtreecommitdiff
path: root/arithmetic_slices2.c
blob: 184d136489aa1adebe240ca3a7f94879209211d6 (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
// 446. Arithmetic Slices II - Subsequence
#include "leetcode.h"
#include "lib/uthash/src/uthash.h"

/*
 * given an integer array 'nums', return the number of all the arithmetic
 * subsequences of 'nums'. a sequence of numbers is called arithmetic if it
 * consists of at least three elements and if the difference between any two
 * consecutive elements is the same. the test cases are generated such that the
 * answer fits in a 32-bit integer.
 */

struct seq_hash {
  long long diff;
  int cnt;
  UT_hash_handle hh;
};

int numberOfArithmeticSlices(int *nums, int nums_size) {
  int ans = 0;
  struct seq_hash **const dp = calloc(nums_size, sizeof(struct seq_hash *));
  for (int end = 1; end < nums_size; ++end) {
    for (int i = 0; i < end; i++) {
      const long long diff = ((long long)nums[end]) - nums[i];
      struct seq_hash *end_entry;
      HASH_FIND(hh, dp[end], &diff, sizeof(diff), end_entry);
      if (!end_entry) {
        end_entry = malloc(sizeof(struct seq_hash));
        end_entry->diff = diff;
        end_entry->cnt = 0;
        HASH_ADD(hh, dp[end], diff, sizeof(end_entry->diff), end_entry);
      }
      struct seq_hash *prev_entry;
      HASH_FIND(hh, dp[i], &diff, sizeof(diff), prev_entry);
      if (!prev_entry)
        ++end_entry->cnt;
      else {
        end_entry->cnt += prev_entry->cnt + 1;
        ans += prev_entry->cnt;
      }
    }
  }
  for (int i = 0; i < nums_size; i++) {
    struct seq_hash *entry, *tmp;
    HASH_ITER(hh, dp[i], entry, tmp) {
      HASH_DEL(dp[i], entry);
      free(entry);
    }
  }
  free(dp);
  return ans;
}

int main() {
  int n1[] = {2, 4, 6, 8, 10}, n2[] = {7, 7, 7, 7, 7};
  printf("%d\n", numberOfArithmeticSlices(n1, ARRAY_SIZE(n1))); // expect: 7
  printf("%d\n", numberOfArithmeticSlices(n2, ARRAY_SIZE(n2))); // expect: 16
}