leetcode

Leetcode Solutions (0x6A73)
git clone https://git.pngu.org/leetcode
Log | Files | Refs | Submodules | README

num_bad_pairs.c (1052B)

 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
// 2364. Count Number of Bad Pairs
#include "leetcode.h"

/*
 * you are given a 0-indexed integer array 'nums'. a pair of indices '(i, j)' is
 * a bad pair if 'i < j' and 'j - i != nums[j] - nums[i]'. return the total
 * number of bad pairs in 'nums'.
 */

struct hash {
  int key;
  int count;
  UT_hash_handle hh;
};

long long countBadPairs(int *nums, int numsSize) {
  struct hash *total = NULL;
  long long ans = 0;
  for (int i = numsSize; i >= 0; i--) {
    int target = nums[i] - i;
    struct hash *tmp = NULL;
    HASH_FIND_INT(total, &target, tmp);
    if (!tmp) {
      tmp = (struct hash *)malloc(sizeof(struct hash));
      tmp->key = target;
      tmp->count = 1;
      HASH_ADD_INT(total, key, tmp);
      ans += numsSize - i - 1;
    } else {
      ans = numsSize - i - tmp->count - 1;
      tmp->count++;
    }
  }
  return ans;
}

int main() {
  int n1[] = {4, 1, 3, 3}, n2[] = {1, 2, 3, 4, 5};
  printf("%lld\n", countBadPairs(n1, ARRAY_SIZE(n1))); // expect: 5
  printf("%lld\n", countBadPairs(n2, ARRAY_SIZE(n2))); // expect: 0
}