aboutsummaryrefslogtreecommitdiff
path: root/num_bad_pairs.c
diff options
context:
space:
mode:
Diffstat (limited to 'num_bad_pairs.c')
-rw-r--r--num_bad_pairs.c41
1 files changed, 41 insertions, 0 deletions
diff --git a/num_bad_pairs.c b/num_bad_pairs.c
new file mode 100644
index 0000000..45292b2
--- /dev/null
+++ b/num_bad_pairs.c
@@ -0,0 +1,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
+}