Count Nice Pairs in an Array

Problem Statement

In this problem, you are provided with an array nums containing non-negative integers. The task is to count the number of "nice" pairs (i, j) in the array where the pair satisfies two conditions:

• The index i is less than index j (0 <= i < j < nums.length).
• The sum of the number at the ith position and the reversed number at the jth position is equal to the sum of the number at the jth position and the reversed number at the ith position (nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])).

The function rev(x) is defined as the reverse of the non-negative integer x. For instance, rev(123) would be 321 and rev(120) would be 21. Your goal is to return the count of such "nice" pairs. Given the potential size, the result should be returned modulo 109 + 7 to ensure the output is manageable.

Examples

Example 1

Input:

nums = [42,11,1,97]

Output:

2

Explanation:

The two pairs are:
- (0,3) : 42 + rev(97) = 42 + 79 = 121, 97 + rev(42) = 97 + 24 = 121.
- (1,2) : 11 + rev(1) = 11 + 1 = 12, 1 + rev(11) = 1 + 11 = 12.

Example 2

Input:

nums = [13,10,35,24,76]

Output:

4

Constraints

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109

Approach and Intuition

To solve this problem, we need to understand the condition under which a pair (i, j) will be considered "nice." Let's break down the condition:

• nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])

This can be re-arranged and simplified to:

• nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])

This means that for any pair (i, j) to be nice, the difference between each number and its reversal must be the same for both i and j. Thus, the approach involves following steps:

1. Calculate diff[i] = nums[i] - rev(nums[i]) for each index i.
2. Use a hash map to count occurrences of each unique difference.
3. For each unique diff value, if it appears count times, the number of nice pairs contributed by this distinct difference is count * (count - 1) / 2 because any two pairs having this diff are nice pairs.
4. Sum up all contributions to get the total number of nice pairs.
5. Return the total count modulo 109 + 7 as per the problem’s constraints.

By decomposing and abstracting the problem using the difference values, it becomes technically feasible to compute the number of nice pairs efficiently, efficient even for large arrays, as we leverage hashing to aggregate and compute pair counts based on unique differences.

Solutions

class Solution {
public:
    int countNicePairs(vector<int>& nums) {
        vector<int> diffs;
        for (int i = 0; i < nums.size(); i++) {
            diffs.push_back(nums[i] - reverseNum(nums[i]));
        }
            
        unordered_map<int, int> countMap;
        int result = 0;
        int MODULO = 1e9 + 7;
        for (int value : diffs) {
            result = (result + countMap[value]) % MODULO;
            countMap[value]++;
        }
            
        return result;
    }
        
    int reverseNum(int num) {
        int reversed = 0;
        while (num > 0) {
            reversed = reversed * 10 + num % 10;
            num /= 10;
        }
            
        return reversed;
    }
};