diff options
author | Jack Sangdahl <[email protected]> | 2025-02-08 18:00:46 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-02-08 18:00:46 -0700 |
commit | 38628b7a294223f7e1caa129f55753183a536fa6 (patch) | |
tree | 5939376ce83a3558c0b76bc8c995f7223809edc5 | |
parent | f72076c568e27c480a1154b527433077e3884aad (diff) | |
download | leetcode-38628b7a294223f7e1caa129f55753183a536fa6.tar.gz leetcode-38628b7a294223f7e1caa129f55753183a536fa6.zip |
2364. count number of bad pairs
-rw-r--r-- | num_bad_pairs.c | 41 | ||||
-rw-r--r-- | num_bad_pairs.cpp | 19 | ||||
-rw-r--r-- | num_bad_pairs.py | 27 | ||||
-rw-r--r-- | num_bad_pairs.rs | 15 |
4 files changed, 86 insertions, 16 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 +} diff --git a/num_bad_pairs.cpp b/num_bad_pairs.cpp index 75ea430..144e6ef 100644 --- a/num_bad_pairs.cpp +++ b/num_bad_pairs.cpp @@ -1,19 +1,20 @@ +// 2364. Count Number of Bad Pairs #include "leetcode.h" /* - * given: 0-indexed integer array - * bad pair: (i, j) if - * i < j && j - i != nums[j] - nums[i] + * 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'. */ class Solution { public: long long countBadPairs(vector<int> &nums) { long long ans = 0; - unordered_map<int, int> um; + unordered_map<int, int> mp; for (int i = 0; i < nums.size(); ++i) { - ans += (long long)i - um[nums[i] - i]; - ++um[nums[i] - i]; + ans += i - mp[nums[i] - i]; + mp[nums[i] - i]++; } return ans; } @@ -21,7 +22,7 @@ public: int main() { Solution obj; - vector<int> nums1 = {4, 1, 3, 3}, nums2 = {1, 2, 3, 4, 5}; - cout << obj.countBadPairs(nums1) << endl; // expect: 5 - cout << obj.countBadPairs(nums2) << endl; // expect: 0 + vector<int> n1 = {4, 1, 3, 3}, n2 = {1, 2, 3, 4, 5}; + printf("%lld\n", obj.countBadPairs(n1)); // expect: 5 + printf("%lld\n", obj.countBadPairs(n2)); // expect: 0 } diff --git a/num_bad_pairs.py b/num_bad_pairs.py new file mode 100644 index 0000000..6f3ae05 --- /dev/null +++ b/num_bad_pairs.py @@ -0,0 +1,27 @@ +# 2364. Count Number of Bad Pairs +from collections import defaultdict + +""" +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'. +""" + + +class Solution(object): + def countBadPairs(self, nums): + """ + :type nums: List[int] + :rtype: int + """ + mp, ans = defaultdict(int), 0 + for i in range(len(nums)): + ans += i - mp[nums[i] - i] + mp[nums[i] - i] += 1 + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.countBadPairs(nums=[4, 1, 3, 3])) + print(obj.countBadPairs(nums=[1, 2, 3, 4, 5])) diff --git a/num_bad_pairs.rs b/num_bad_pairs.rs index 8e1e7dd..88119d8 100644 --- a/num_bad_pairs.rs +++ b/num_bad_pairs.rs @@ -1,10 +1,11 @@ +// 2364. Count Number of Bad Pairs use std::collections::HashMap; struct Solution; /* - * given: 0-indexed integer array - * bad pair: (i, j) if - * i < j && j - i != nums[j] - nums[i] + * 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'. */ impl Solution { @@ -22,8 +23,8 @@ impl Solution { } fn main() { - let nums1 = vec![4,1,3,3]; - let nums2 = vec![1,2,3,4,5]; - println!("{}", Solution::count_bad_pairs(nums1)); //expect: 5 - println!("{}", Solution::count_bad_pairs(nums2)); //expect: 0 + let n1 = vec![4, 1, 3, 3]; + let n2 = vec![1, 2, 3, 4, 5]; + println!("{}", Solution::count_bad_pairs(n1)); //expect: 5 + println!("{}", Solution::count_bad_pairs(n2)); //expect: 0 } |