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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Nice Pairs in an Array

Number: 1925

Difficulty: Medium

Paid? No

Companies: Uber, Amazon, Microsoft, Yahoo, Block

Problem Description

Given an array of non-negative integers, a pair of indices (i, j) is defined as nice if 0 <= i < j and the following equation holds: nums[i] + rev(nums[j]) == nums[j] + rev(nums[i]), where rev(x) represents the reverse of the integer x. The task is to count the total number of nice pairs in the array and return the count modulo 10^9 + 7.

Key Insights

  • The core observation is that the condition can be rearranged to (nums[i] - rev(nums[i])) == (nums[j] - rev(nums[j])).
  • This allows grouping numbers by the computed difference d = x - rev(x).
  • For each group, if there are count elements, they can form count*(count-1)/2 nice pairs.
  • A hash map can be used for efficient counting and grouping.

Space and Time Complexity

Time Complexity: O(n) where n is the number of elements in the array, since we iterate over the array once. Space Complexity: O(n) in the worst-case scenario, for the hash map storing counts for each unique computed difference.

Solution

We compute a transformed value for each number as d = number - rev(number). The condition for a pair to be nice translates into both elements having the same d value. We use a hash map (or dictionary) to maintain the frequency of each d value. For each number in the array, we update the frequency and count the nice pairs formed with elements already seen having the same d value. The answer is obtained by summing these pair counts and then taking modulo 10^9 + 7.

Code Solutions

# Python solution with detailed comments

class Solution:
    def countNicePairs(self, nums: List[int]) -> int:
        MOD = 10**9 + 7  # Modulo value as specified in the problem
        count_map = {}  # Hash map to store frequency of d value (num - rev(num))
        nice_pairs = 0  # Counter for the number of nice pairs
        
        # Helper function to reverse an integer
        def reverse_num(x: int) -> int:
            return int(str(x)[::-1])
        
        # Process each number in the array
        for num in nums:
            # Compute the reversed number and the difference d = num - rev(num)
            rev_val = reverse_num(num)
            diff = num - rev_val
            
            # If the same difference exists in the map, add the frequency count to nice_pairs
            if diff in count_map:
                nice_pairs = (nice_pairs + count_map[diff]) % MOD
                count_map[diff] += 1  # Increment count for this diff
            else:
                count_map[diff] = 1  # Initialize count for new diff
                
        return nice_pairs
← Back to All Questions