9_Count_Number_of_Bad_Pairs.cpp

// 2364. Count Number of Bad Pairs

// 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.

 
// Example 1:

// Input: nums = [4,1,3,3]
// Output: 5
// Explanation: The pair (0, 1) is a bad pair since 1 - 0 != 1 - 4.
// The pair (0, 2) is a bad pair since 2 - 0 != 3 - 4, 2 != -1.
// The pair (0, 3) is a bad pair since 3 - 0 != 3 - 4, 3 != -1.
// The pair (1, 2) is a bad pair since 2 - 1 != 3 - 1, 1 != 2.
// The pair (2, 3) is a bad pair since 3 - 2 != 3 - 3, 1 != 0.
// There are a total of 5 bad pairs, so we return 5.
// Example 2:

// Input: nums = [1,2,3,4,5]
// Output: 0
// Explanation: There are no bad pairs.
 

// Constraints:

// 1 <= nums.length <= 105
// 1 <= nums[i] <= 109

class Solution
{
public:
    long long countBadPairs(vector<int> &nums)
    {
        unordered_map<int, int> bag;
        long long count = 0, n = nums.size();
        for (int i = 0; i < n; i++)
        {
            int key = nums[i] - i;
            count += bag[key];
            bag[key]++;
        }

        return (n * (n - 1)) / 2 - count;
    }
};

/*
This code finds the number of bad pairs in an array. A bad pair is when j-i != nums[j]-nums[i] where i<j.
The solution uses the fact that if j-i = nums[j]-nums[i], then nums[j]-j = nums[i]-i.
It stores nums[i]-i in a hashmap and counts frequencies.
For each element, it adds the count of previous elements with same difference to get good pairs.
Finally, it subtracts good pairs from total possible pairs (n*(n-1))/2 to get bad pairs.
Time complexity is O(n) and space complexity is O(n).
*/