Count Index Pairs That Disagree with Their Value Difference
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
A pair of indices `(i, j)` is bad when `i < j` and `j - i != nums[j] - nums[i]`. Return the number of bad pairs in `nums` as a `long long`.
```cpp
class Solution {
public:
long long countBadPairs(vector<int>& nums);
};
```
### Examples
**Example 1:**
```text
Input: nums = [2,3,5]
Output: 2
Explanation: Pair (0,1) is good because both differences equal 1. The other two pairs are bad.
```
**Example 2:**
```text
Input: nums = [7,7,7]
Output: 3
Explanation: Every positive index difference differs from the zero value difference, so all three pairs are bad.
```
### Constraints
- `1 <= nums.length <= 100000`.
- `1 <= nums[i] <= 10^9`.
### Clarifying Questions
- Are pairs based on indices or distinct values? Indices; repeated values still create separate pairs.
- Is `(j, i)` counted too? No; only `i < j`.
- Can the result exceed a 32-bit integer? Yes; there may be nearly five billion pairs.
```hint Check the boundary
For two equal values at different indices, compare their value difference with their index difference.
```
Overview: Count index pairs whose index difference differs from their value difference, including separate occurrences of repeated values.