Count Nice Pairs in an Array
Problem
rev(x) reverses x's digits. Count pairs (i, j) with inums = [42,11,1,97]2
def count_nice_pairs(nums):
MOD = 10**9 + 7
from collections import Counter
def rev(x): return int(str(x)[::-1])
cnt = Counter()
ans = 0
for x in nums:
k = x - rev(x)
ans = (ans + cnt[k]) % MOD
cnt[k] += 1
return ansfunction countNicePairs(nums) {
const MOD = 1000000007n;
const cnt = new Map();
let ans = 0n;
function rev(x) { return parseInt(String(x).split('').reverse().join(''), 10); }
for (const x of nums) {
const k = x - rev(x);
ans = (ans + BigInt(cnt.get(k) || 0)) % MOD;
cnt.set(k, (cnt.get(k) || 0) + 1);
}
return Number(ans);
}class Solution {
int rev(int x) { int r = 0; while (x > 0) { r = r * 10 + x % 10; x /= 10; } return r; }
public int countNicePairs(int[] nums) {
long MOD = 1_000_000_007L, ans = 0;
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : nums) {
int k = x - rev(x);
ans = (ans + cnt.getOrDefault(k, 0)) % MOD;
cnt.merge(k, 1, Integer::sum);
}
return (int) ans;
}
}int rev(int x) { int r = 0; while (x > 0) { r = r * 10 + x % 10; x /= 10; } return r; }
int countNicePairs(vector<int>& nums) {
const long MOD = 1000000007;
unordered_map<int,int> cnt;
long ans = 0;
for (int x : nums) {
int k = x - rev(x);
ans = (ans + cnt[k]) % MOD;
cnt[k]++;
}
return (int) ans;
}Explanation
The condition nums[i] + rev(nums[j]) == nums[j] + rev(nums[i]) looks messy, but a little algebra makes it simple. Rearrange it to nums[i] - rev(nums[i]) == nums[j] - rev(nums[j]). So two elements form a nice pair exactly when their value of x - rev(x) is the same.
That turns the problem into counting pairs that share a key. We compute the key k = x - rev(x) for each number and use a hash map cnt to track how many earlier numbers had each key.
As we scan left to right, before inserting the current number we add cnt[k] to the answer — that is the number of earlier elements it can pair with. Then we bump cnt[k] += 1 so future elements can pair with this one too.
Example: nums = [42,11,1,97]. Keys are 42-24=18, 11-11=0, 1-1=0, 97-79=18. The two zeros form one pair and the two eighteens form another, so the answer is 2. The result is taken mod 1e9+7 to stay in range.
Each element is processed with one map lookup, so the whole count is a single linear pass.