New Problem Solution -"1711. Count Good Meals"

haoel · haoel · commit 0157340a3fdc · 2021-03-30T19:44:40.000+08:00
diff --git a/README.md b/README.md
@@ -63,6 +63,7 @@ LeetCode
 |1725|[Number Of Rectangles That Can Form The Largest Square](https://leetcode.com/problems/number-of-rectangles-that-can-form-the-largest-square/) | [C++](./algorithms/cpp/numberOfRectanglesThatCanFormTheLargestSquare/NumberOfRectanglesThatCanFormTheLargestSquare.cpp)|Easy|
 |1717|[Maximum Score From Removing Substrings](https://leetcode.com/problems/maximum-score-from-removing-substrings/) | [C++](./algorithms/cpp/maximumScoreFromRemovingSubstrings/MaximumScoreFromRemovingSubstrings.cpp)|Medium|
 |1716|[Calculate Money in Leetcode Bank](https://leetcode.com/problems/calculate-money-in-leetcode-bank/) | [C++](./algorithms/cpp/calculateMoneyInLeetcodeBank/CalculateMoneyInLeetcodeBank.cpp)|Easy|
+|1711|[Count Good Meals](https://leetcode.com/problems/count-good-meals/) | [C++](./algorithms/cpp/countGoodMeals/CountGoodMeals.cpp)|Medium|
 |1710|[Maximum Units on a Truck](https://leetcode.com/problems/maximum-units-on-a-truck/) | [C++](./algorithms/cpp/maximumUnitsOnATruck/MaximumUnitsOnATruck.cpp)|Easy|
 |1625|[Lexicographically Smallest String After Applying Operations](https://leetcode.com/problems/lexicographically-smallest-string-after-applying-operations/) | [C++](./algorithms/cpp/lexicographicallySmallestStringAfterApplyingOperations/LexicographicallySmallestStringAfterApplyingOperations.cpp)|Medium|
 |1624|[Largest Substring Between Two Equal Characters](https://leetcode.com/problems/largest-substring-between-two-equal-characters/) | [C++](./algorithms/cpp/largestSubstringBetweenTwoEqualCharacters/LargestSubstringBetweenTwoEqualCharacters.cpp)|Easy|
diff --git a/algorithms/cpp/countGoodMeals/CountGoodMeals.cpp b/algorithms/cpp/countGoodMeals/CountGoodMeals.cpp
@@ -0,0 +1,69 @@
+// Source : https://leetcode.com/problems/count-good-meals/
+// Author : Hao Chen
+// Date   : 2021-03-30
+
+/***************************************************************************************************** 
+ *
+ * A good meal is a meal that contains exactly two different food items with a sum of deliciousness 
+ * equal to a power of two.
+ * 
+ * You can pick any two different foods to make a good meal.
+ * 
+ * Given an array of integers deliciousness where deliciousness[i] is the deliciousness of the i^​​​​​​
+ * th​​​​​​​​ item of food, return the number of different good meals you can make from this list 
+ * modulo 10^9 + 7.
+ * 
+ * Note that items with different indices are considered different even if they have the same 
+ * deliciousness value.
+ * 
+ * Example 1:
+ * 
+ * Input: deliciousness = [1,3,5,7,9]
+ * Output: 4
+ * Explanation: The good meals are (1,3), (1,7), (3,5) and, (7,9).
+ * Their respective sums are 4, 8, 8, and 16, all of which are powers of 2.
+ * 
+ * Example 2:
+ * 
+ * Input: deliciousness = [1,1,1,3,3,3,7]
+ * Output: 15
+ * Explanation: The good meals are (1,1) with 3 ways, (1,3) with 9 ways, and (1,7) with 3 ways.
+ * 
+ * Constraints:
+ * 
+ * 	1 <= deliciousness.length <= 10^5
+ * 	0 <= deliciousness[i] <= 2^20
+ ******************************************************************************************************/
+
+class Solution {
+public:
+    int countPairs(vector<int>& deliciousness) {
+        const int MAX_EXP = 22;
+        int pow2[MAX_EXP];
+        for (int i=0; i<MAX_EXP; i++){
+            pow2[i] = 1 << i;
+            //cout << pow2[i] << ", ";
+        }
+        
+        unordered_map<int, int> stat;
+        int big = 0;
+        for(auto& d: deliciousness){
+            stat[d]++;
+
+        }
+
+        long m = 0;
+        for(auto& d: deliciousness){
+            for(int i=MAX_EXP-1; i>=0 && pow2[i] >= d; i--){
+                int x = pow2[i] - d;
+                if ( stat.find(x) != stat.end() ){
+                    m += (x==d) ? stat[x]-1 : stat[x];
+                }
+            }
+        }
+        
+        // remove the duplication - m/2, 
+        // because both [1,3] and [3,1] are counted.
+        return (m/2) % 1000000007;
+    }
+};
