We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

Count Nice Pairs in an Array

Difficulty: Medium

Problem Description

You are given an array nums that consists of non-negative integers. A pair of indices (i, j) is nice if it satisfies 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.

Key Insights

The condition for a nice pair can be rearranged to nums[i] - rev(nums[i]) == nums[j] - rev(nums[j]).
This means that we need to find pairs of indices where the difference between the number and its reverse is the same.
We can use a hash map to count occurrences of each difference.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we will:

Create a function to reverse the digits of a number.
Iterate through the array while calculating the difference between each number and its reverse.
Use a hash map to keep track of how many times each difference has occurred.
For each occurrence of a difference, the number of nice pairs can be computed based on the count of that difference seen so far.

Code Solutions

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

def countNicePairs(nums):
    modulo = 10**9 + 7
    count = {}
    nice_pairs = 0
    
    for num in nums:
        diff = num - rev(num)
        if diff in count:
            nice_pairs = (nice_pairs + count[diff]) % modulo
            count[diff] += 1
        else:
            count[diff] = 1
    
    return nice_pairs

← Back to All Questions