1814. Count Nice Pairs in an Array
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 109 + 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 <= 105
0 <= nums[i] <= 109
Solutions
Solution: Hash Map
- Time complexity: O(n)
- Space complexity: O(n)
JavaScript
js
/**
* @param {number[]} nums
* @return {number}
*/
const countNicePairs = function (nums) {
const MODULO = 10 ** 9 + 7;
const uniqueNums = [...new Set(nums)];
const countMap = new Map();
const reverseMap = uniqueNums.reduce((map, num) => {
return (map[num] = +`${num}`.split('').reverse().join('')), map;
}, {});
let result = 0;
for (const num of nums) {
const diff = num - reverseMap[num];
const count = countMap.get(diff) ?? 0;
if (count) {
result += count;
result %= MODULO;
}
countMap.set(diff, count + 1);
}
return result;
};