Problem

You are given an array nums that consists of non-negative integers. Let us define rev(x) as the reverse of the non-negative integer x. For example, rev(123) = 321, and rev(120) = 21. A pair of indices (i, j) is nice if it satisfies all of the following conditions:

  • 0 <= i < j < nums.length
  • nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])

Return the number of nice pairs of indices. Since that number can be too large, return it modulo 10^9 + 7.

Examples

Example 1:

1
2
3
4
5

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:

1
2

Input: nums = [13,10,35,24,76]
Output: 4

Solution

Method 1 - Counting Nice Pairs Using Differences and Hashing

  1. Conditions for a “Nice” Pair:
    • 0 <= i < j < nums.length
    • nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])
  2. Key Insight:
    • The condition nums[i] + rev(nums[j]) == nums[j] + rev(nums[i]) is equivalent to nums[i] - rev(nums[i]) == nums[j] - rev(nums[j]).
  3. Algorithm:
    • Compute diff[i] = nums[i] - rev(nums[i]) for each i.
    • Count the frequency of each value in diff.
    • The number of pairs with the same value of diff can be computed using combinatorial counting. Here is the approach:
  4. Compute Reversed Digits: Implement a helper function rev(x) to reverse the digits of a number.
  5. Compute Differences: For each number in nums, compute diff[i] = nums[i] - rev(nums[i]).
  6. Count Pairs: Use a hash map to count the frequency of each unique value in diff. For each unique value with frequency f, the number of pairs is f * (f - 1) / 2.
  7. Modulo Operation: Since the result needs to be modulo (10^9 + 7), ensure all operations respect this constraint.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

public class Solution {
    public int countNicePairs(int[] nums) {
        final int MOD = 1000000007;

        Map<Integer, Integer> diffCount = new HashMap<>();
        int nicePairs = 0;

        for (int num : nums) {
            int revNum = reverse(num);
            int diff = num - revNum;

            diffCount.put(diff, diffCount.getOrDefault(diff, 0) + 1);
        }

        for (int count : diffCount.values()) {
            if (count > 1) {
                nicePairs = (nicePairs + (count * (count - 1) / 2) % MOD) % MOD;
            }
        }

        return nicePairs;
    }

    private int reverse(int num) {
        int rev = 0;
        while (num > 0) {
            rev = rev * 10 + num % 10;
            num /= 10;
        }
        return rev;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        int[] nums1 = {42, 11, 1, 97};
        System.out.println("Number of nice pairs: "
            + solution.countNicePairs(nums1)); // Output: 2

        int[] nums2 = {13, 10, 35, 24, 76};
        System.out.println("Number of nice pairs: "
            + solution.countNicePairs(nums2)); // Output: 0
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

def countNicePairs(nums):
    MOD = 10**9 + 7

    def rev(x):
        return int(str(x)[::-1])

    diff_count = {}
    nice_pairs = 0

    for num in nums:
        diff = num - rev(num)
        if diff in diff_count:
            diff_count[diff] += 1
        else:
            diff_count[diff] = 1

    for count in diff_count.values():
        if count > 1:
            nice_pairs += count * (count - 1) // 2
            nice_pairs %= MOD

    return nice_pairs

Complexity

  • Time: O(n), where (n) is the length of the array. This is because each operation (reversing a number, calculating differences, and counting frequencies) is done in linear time.
  • Space: O(n), due to the auxiliary space used by the hash map to store differences and their frequencies.