New Problem Solution - "1814. Count Nice Pairs in an Array"

haoel · haoel · commit 9d268cd74684 · 2021-04-06T13:39:20.000+08:00
diff --git a/README.md b/README.md
@@ -13,6 +13,7 @@ LeetCode
 |1818|[Minimum Absolute Sum Difference](https://leetcode.com/problems/minimum-absolute-sum-difference/) | [C++](./algorithms/cpp/minimumAbsoluteSumDifference/MinimumAbsoluteSumDifference.cpp)|Medium|
 |1817|[Finding the Users Active Minutes](https://leetcode.com/problems/finding-the-users-active-minutes/) | [C++](./algorithms/cpp/findingTheUsersActiveMinutes/FindingTheUsersActiveMinutes.cpp)|Medium|
 |1816|[Truncate Sentence](https://leetcode.com/problems/truncate-sentence/) | [C++](./algorithms/cpp/truncateSentence/TruncateSentence.cpp)|Easy|
+|1814|[Count Nice Pairs in an Array](https://leetcode.com/problems/count-nice-pairs-in-an-array/) | [C++](./algorithms/cpp/countNicePairsInAnArray/CountNicePairsInAnArray.cpp)|Medium|
 |1813|[Sentence Similarity III](https://leetcode.com/problems/sentence-similarity-iii/) | [C++](./algorithms/cpp/sentenceSimilarity/SentenceSimilarity.III.cpp)|Medium|
 |1812|[Determine Color of a Chessboard Square](https://leetcode.com/problems/determine-color-of-a-chessboard-square/) | [C++](./algorithms/cpp/determineColorOfAChessboardSquare/DetermineColorOfAChessboardSquare.cpp)|Easy|
 |1808|[Maximize Number of Nice Divisors](https://leetcode.com/problems/maximize-number-of-nice-divisors/) | [C++](./algorithms/cpp/maximizeNumberOfNiceDivisors/MaximizeNumberOfNiceDivisors.cpp)|Hard|
diff --git a/algorithms/cpp/countNicePairsInAnArray/CountNicePairsInAnArray.cpp b/algorithms/cpp/countNicePairsInAnArray/CountNicePairsInAnArray.cpp
@@ -0,0 +1,86 @@
+// Source : https://leetcode.com/problems/count-nice-pairs-in-an-array/
+// Author : Hao Chen
+// Date   : 2021-04-06
+
+/***************************************************************************************************** 
+ *
+ * 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 
+ * 10^9 + 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 <= 10^5
+ * 	0 <= nums[i] <= 10^9
+ ******************************************************************************************************/
+
+class Solution {
+private:
+    int rev(int n) {
+        int x = 0;
+        while(n > 0) {
+            x = x*10 + (n % 10);
+            n /= 10;
+        }
+        return x;
+    }
+
+public:
+    int countNicePairs(vector<int>& nums) {
+        return countNicePairs02(nums);
+        return countNicePairs01(nums);
+    }
+    int countNicePairs01(vector<int>& nums) {
+        // suppose n' = rev(n) 
+        // define:  a + b' == b + a'
+        //   then:  a - a' == b - b'
+        
+        unordered_map<int, int> stat;
+        for(auto& n : nums) {
+            stat[n-rev(n)]++;
+            
+        }
+        
+        //if there are n elements  has same value, 
+        // then there are  n*(n-1)/2 unique pairs.
+        int result = 0;
+        for(auto& [n, cnt] : stat) {
+            result  =  (result + cnt * (cnt -1l) / 2)  % 1000000007;
+        }
+        return result;
+    }
+    
+    int countNicePairs02(vector<int>& nums) {
+        // suppose n' = rev(n) 
+        // define:  a + b' == b + a'
+        //   then:  a - a' == b - b'
+        int result = 0;
+        unordered_map<int, int> stat;
+        for(auto& n : nums) {
+            int delta = n-rev(n);
+            stat[delta]++;
+            result = (result + (stat[delta] - 1l)) % 1000000007 ;
+        }
+        
+        return result ;
+    }
+};
