Count Nice Pairs in an Array

MEDIUM

Description

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⁹ + 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 <= 10⁵
0 <= nums[i] <= 10⁹

Approaches

Checkout 2 different approaches to solve Count Nice Pairs in an Array. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

This approach directly translates the problem statement into code. It involves checking every possible pair of indices (i, j) where i < j to see if they form a "nice pair". For each pair, it computes the reverse of the corresponding numbers and verifies if the condition nums[i] + rev(nums[j]) == nums[j] + rev(nums[i]) holds true.

Algorithm

Initialize a counter count to 0.
Define the modulo constant MOD = 1_000_000_007.
Create a helper function rev(int n) that returns the reverse of the integer n.
Use a nested loop structure. The outer loop iterates with index i from 0 to nums.length - 2.
The inner loop iterates with index j from i + 1 to nums.length - 1.
Inside the inner loop, for each pair (nums[i], nums[j]), check if the nice pair condition nums[i] + rev(nums[j]) == nums[j] + rev(nums[i]) is satisfied.
To avoid potential integer overflow during the check, cast the numbers to a long before addition.
If the condition is true, increment the count.
After the loops complete, return count % MOD.

The brute-force method uses two nested loops to generate all unique pairs of indices (i, j) such that 0 <= i < j < nums.length. The outer loop runs from i = 0 to n-1, and the inner loop from j = i + 1 to n-1, where n is the length of the array. Inside the inner loop, we first need a helper function rev(x) to compute the reverse of an integer. This function can be implemented by repeatedly taking the last digit of the number and building the reversed number. We then check if nums[i] + rev(nums[j]) == nums[j] + rev(nums[i]). If the condition is met, we increment a counter. Since the total count can be very large, the counter should be a long to avoid overflow. Finally, we return the total count modulo 10^9 + 7.

class Solution {
    private int rev(int n) {
        int reversed = 0;
        while (n > 0) {
            reversed = reversed * 10 + n % 10;
            n /= 10;
        }
        return reversed;
    }

    public int countNicePairs(int[] nums) {
        int n = nums.length;
        long count = 0;
        int MOD = 1_000_000_007;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((long)nums[i] + rev(nums[j]) == (long)nums[j] + rev(nums[i])) {
                    count++;
                }
            }
        }
        return (int)(count % MOD);
    }
}

Complexity Analysis

Time Complexity: O(N^2 * log(M)), where N is the length of the `nums` array and M is the maximum value in `nums`. The two nested loops result in O(N^2) iterations. Inside each iteration, the `rev()` function is called, which takes logarithmic time proportional to the number of digits in the number M.Space Complexity: O(1) extra space, as we only use a few variables to store the count and loop indices.

Pros and Cons

Pros:

Simple to understand and implement directly from the problem definition.
Requires minimal extra space.

Cons:

Extremely inefficient for large inputs due to its quadratic time complexity.
Will result in a 'Time Limit Exceeded' (TLE) error on most competitive programming platforms for the given constraints.

Code Solutions

Checking out 5 solutions in different languages for Count Nice Pairs in an Array. Click on different languages to view the code.

public class Solution {
    public int CountNicePairs(int[] nums) {
        Dictionary < int, int > cnt = new Dictionary < int, int > ();
        foreach(int x in nums) {
            int y = x - Rev(x);
            cnt[y] = cnt.GetValueOrDefault(y, 0) + 1;
        }
        int mod = (int) 1 e9 + 7;
        long ans = 0;
        foreach(int v in cnt.Values) {
            ans = (ans + (long) v * (v - 1) / 2) % mod;
        }
        return (int) ans;
    }
    private int Rev(int x) {
        int y = 0;
        while (x > 0) {
            y = y * 10 + x % 10;
            x /= 10;
        }
        return y;
    }
}

Video Solution

Watch the video walkthrough for Count Nice Pairs in an Array

Patterns:

MathCounting

Data Structures:

ArrayHash Table

Companies:

Block |