Leetcode 1814. Count Nice Pairs in an Array Solution

Problem Explanation

You are given an array nums containing non-negative integers. You need to find the number of "nice" pairs of indices (i, j) in the array. A pair of indices is considered "nice" if it satisfies the following two conditions:

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

where rev(x) is the reverse of the non-negative integer x. For example, rev(123) = 321 and rev(120) = 21.

The goal is to return the total number of nice pairs, modulo 10^9 + 7.

Let's walk through an example:

1Input: nums = [42, 11, 1, 97]
2Output: 2

The two pairs of nice indices are:

• (0, 3): nums[0] + rev(nums[3]) = 42 + rev(97) = 42 + 79 = 121, nums[3] + rev(nums[0]) = 97 + rev(42) = 97 + 24 = 121
• (1, 2): nums[1] + rev(nums[2]) = 11 + rev(1) = 11 + 1 = 12, nums[2] + rev(nums[1]) = 1 + rev(11) = 1 + 11 = 12

Solution Approach

The given problem can be solved using a Hash Map data structure. First, we create an unordered_map that will store the count of each num - rev(num) for each element in nums. Next, to count the number of nice pairs, we iterate through the hash map and calculate the combinations of each count: freq * (freq - 1) / 2. Increment the final result (ans) with these counts and return the final answer after taking the modulus of each increment at every step.

To reverse a number, we define a rev helper function, that takes an integer n and returns the reverse of the n.

Python Solution

1class Solution:
2    def countNicePairs(self, nums: List[int]) -> int:
3        kMod = 1_000_000_007
4        ans = 0
5        count = {}
6        
7        def rev(n: int) -> int:
8            x = 0
9            while n:
10                x = x * 10 + (n % 10)
11                n //= 10
12            return x
13        
14        for num in nums:
15            count[num - rev(num)] = count.get(num - rev(num), 0) + 1
16
17        for freq in count.values():
18            ans += freq * (freq - 1) // 2
19            ans %= kMod
20
21        return ans

Java Solution

1import java.util.HashMap;
2
3class Solution {
4    public int countNicePairs(int[] nums) {
5        final int kMod = 1_000_000_007;
6        long ans = 0;
7        HashMap<Integer, Long> count = new HashMap<>();
8
9        for (int num : nums) {
10            int diff = num - rev(num);
11            count.put(diff, count.getOrDefault(diff, 0L) + 1);
12        }
13
14        for (long freq : count.values()) {
15            ans += freq * (freq - 1) / 2;
16            ans %= kMod;
17        }
18
19        return (int) ans;
20    }
21
22    private int rev(int n) {
23        int x = 0;
24        while (n != 0) {
25            x = x * 10 + (n % 10);
26            n /= 10;
27        }
28        return x;
29    }
30}

JavaScript Solution

1class Solution {
2    countNicePairs(nums) {
3        const kMod = 1_000_000_007;
4        let ans = 0;
5        const count = new Map();
6
7        for (const num of nums) {
8            const diff = num - this.rev(num);
9            count.set(diff, (count.get(diff) || 0) + 1);
10        }
11
12        for (const freq of count.values()) {
13            ans += freq * (freq - 1) / 2;
14            ans %= kMod;
15        }
16
17        return ans;
18    }
19
20    rev(n) {
21        let x = 0;
22        while (n) {
23            x = x * 10 + (n % 10);
24            n = Math.floor(n / 10);
25        }
26        return x;
27    }
28}

C++ Solution

1#include <unordered_map>
2#include <vector>
3
4class Solution {
5 public:
6  int countNicePairs(std::vector<int>& nums) {
7    constexpr int kMod = 1'000'000'007;
8    long ans = 0;
9    std::unordered_map<int, long> count;
10
11    for (const int num : nums) {
12      ++count[num - rev(num)];
13    }
14
15    for (const auto& elem : count) {
16      ans += elem.second * (elem.second - 1) / 2;
17      ans %= kMod;
18    }
19
20    return ans;
21  }
22
23 private:
24  int rev(int n) {
25    int x = 0;
26    while (n) {
27      x = x * 10 + (n % 10);
28      n /= 10;
29    }
30    return x;
31  }
32};

C# Solution

1using System.Collections.Generic;
2
3public class Solution {
4    public int CountNicePairs(int[] nums) {
5        const int kMod = 1_000_000_007;
6        long ans = 0;
7        Dictionary<int, long> count = new Dictionary<int, long>();
8
9        foreach (int num in nums) {
10            int diff = num - Rev(num);
11            if (!count.ContainsKey(diff)) {
12                count[diff] = 0;
13            }
14            count[diff]++;
15        }
16
17        foreach (long freq in count.Values) {
18            ans += freq * (freq - 1) / 2;
19            ans %= kMod;
20        }
21
22        return (int) ans;
23    }
24
25    private int Rev(int n) {
26        int x = 0;
27        while (n != 0) {
28            x = x * 10 + (n % 10);
29            n /= 10;
30        }
31        return x;
32    }
33}
34
35```In conclusion, the given problem can be solved by iterating through the input array while counting the occurrences of the difference between each number and its reverse. Then, by iterating through the counts and incrementing the final result with the factorial of the count divided by 2, the number of nice pairs can be calculated. To reverse a number, we defined a helper function `rev(n)` that takes an integer `n` as input and returns its reverse. We have provided solutions in Python, Java, JavaScript, C++, and C#.