1814. Count Nice Pairs in an Array Medium

1/**
2 * [1814] Count Nice Pairs in an Array
3 *
4 * 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:
5 * 
6 * 0 <= i < j < nums.length
7 * nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])
8 * 
9 * Return the number of nice pairs of indices. Since that number can be too large, return it modulo 10^9 + 7.
10 *  
11 * Example 1:
12 * 
13 * Input: nums = [42,11,1,97]
14 * Output: 2
15 * Explanation: The two pairs are:
16 *  - (0,3) : 42 + rev(97) = 42 + 79 = 121, 97 + rev(42) = 97 + 24 = 121.
17 *  - (1,2) : 11 + rev(1) = 11 + 1 = 12, 1 + rev(11) = 1 + 11 = 12.
18 * 
19 * Example 2:
20 * 
21 * Input: nums = [13,10,35,24,76]
22 * Output: 4
23 * 
24 *  
25 * Constraints:
26 * 
27 * 1 <= nums.length <= 10^5
28 * 0 <= nums[i] <= 10^9
29 * 
30 */
31pub struct Solution {}
32
33// problem: https://leetcode.com/problems/count-nice-pairs-in-an-array/
34// discuss: https://leetcode.com/problems/count-nice-pairs-in-an-array/discuss/?currentPage=1&orderBy=most_votes&query=
35
36// submission codes start here
37use std::collections::HashMap;
38
39impl Solution {
40    const MOD: i64 = 1000000007;
41    pub fn count_nice_pairs(nums: Vec<i32>) -> i32 {
42        let mut map: HashMap<i32, i32> = HashMap::new();
43        let mut count: HashMap<i32, i32> = HashMap::new();
44        for n in nums {
45            let t = Self::rev(n, &mut map);
46            count.entry(n - t).and_modify(|x| {*x += 1;}).or_insert(1);
47        }
48        let mut sum = 0i64;
49        for (_, value) in count {
50            sum = (sum + value as i64 * (value as i64 - 1) / 2 % Self::MOD) % Self::MOD;
51        }
52        sum as i32
53    }
54
55    fn rev(x: i32, map: &mut HashMap<i32, i32>) -> i32 {
56        *map.entry(x).or_insert_with(|| {
57            let mut result = 0;
58            let mut n = x;
59            while n > 0 {
60                result = result * 10 + n % 10;
61                n /= 10;
62            }
63            result
64        })
65    }
66}
67
68// submission codes end
69
70#[cfg(test)]
71mod tests {
72    use super::*;
73
74    #[test]
75    fn test_1814() {
76        assert_eq!(Solution::count_nice_pairs(vec![13,10,35,24,76]), 4);}
77}
78