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:
0 <= i < j < nums.length
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#.