{x}
blog image

Count Nice Pairs in an Array

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 109 + 7.

 

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

Solution Explanation:

The problem asks to count the number of "nice pairs" in an array. A nice pair (i, j) satisfies two conditions:

  1. 0 <= i < j < nums.length (i and j are valid indices and i comes before j).
  2. nums[i] + rev(nums[j]) == nums[j] + rev(nums[i]) (a specific mathematical relationship between the elements at those indices and their reverses holds).

Core Idea: The key to an efficient solution lies in simplifying the second condition. Let's manipulate the equation:

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

This can be rewritten as:

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

This means that for a pair to be "nice", the difference between an element and its reverse must be the same for both elements in the pair.

Algorithm:

  1. Reverse Function: Create a helper function rev(x) to reverse an integer.

  2. Difference Calculation: For each number nums[i] in the input array, calculate the difference diff = nums[i] - rev(nums[i]).

  3. Counting Differences: Use a hash map (or dictionary) to count the occurrences of each difference. This efficiently tracks how many numbers have the same difference.

  4. Counting Nice Pairs: For each difference diff found in the hash map, if there are count occurrences of that difference, the number of nice pairs formed using numbers with that difference is given by the combination formula: count * (count - 1) / 2. This is because any two numbers with the same difference will form a nice pair.

  5. Modulo Operation: Remember to apply the modulo operation (% 10^9 + 7) throughout the calculation to prevent integer overflow.

Time and Space Complexity:

  • Time Complexity: O(n log m), where n is the length of nums and m is the maximum value in nums. The dominant factor is iterating through the array and reversing integers (reversing takes at most log m time). Hash map operations are typically O(1) on average.
  • Space Complexity: O(n) in the worst case, as the hash map might store up to n unique differences.

Code Examples (Python):

from collections import Counter
 
def rev(x):
    y = 0
    while x:
        y = y * 10 + x % 10
        x //= 10
    return y
 
def countNicePairs(nums):
    diffs = Counter(num - rev(num) for num in nums)
    mod = 10**9 + 7
    ans = 0
    for count in diffs.values():
        ans = (ans + count * (count - 1) // 2) % mod
    return ans

The other languages provided follow the same logic, adapting the syntax and data structures accordingly. The core steps (reverse, difference calculation, counting, combination calculation, and modulo operation) remain consistent across all implementations.