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
struct Solution;
use std::collections::HashMap;
const MOD: i64 = 1_000_000_007;
impl Solution {
fn count_nice_pairs(nums: Vec<i32>) -> i32 {
let mut hm: HashMap<i32, i32> = HashMap::new();
let mut res: i64 = 0;
for x in nums {
let diff = x - rev(x);
let count = hm.entry(diff).or_default();
res += *count as i64;
*count += 1;
}
(res % MOD) as i32
}
}
fn rev(mut x: i32) -> i32 {
let mut digits: Vec<i32> = vec![];
while x > 0 {
digits.push(x % 10);
x /= 10;
}
let mut res = 0;
for x in digits {
res *= 10;
res += x;
}
res
}
#[test]
fn test() {
let nums = vec![42, 11, 1, 97];
let res = 2;
assert_eq!(Solution::count_nice_pairs(nums), res);
let nums = vec![13, 10, 35, 24, 76];
let res = 4;
assert_eq!(Solution::count_nice_pairs(nums), res);
}