leetcode

commit ac0a339571cb3b7fa386b1b519989c61952b87e9
parent e32bf0d88aba53d78893d811d8fb693db2751f05
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Thu, 23 May 2024 19:38:26 +0200

Daily Problem

Diffstat:
A
Problems/2597.cpp
 | 
23
+++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 24 insertions(+), 0 deletions(-)
diff --git a/Problems/2597.cpp b/Problems/2597.cpp
@@ -0,0 +1,23 @@
+class Solution {
+  public:
+    int beautifulSubsets(const vector<int> &nums, const int g) const {
+        const int n = size(nums);
+        vector<map<int, int>> mat(g);
+        int res = 1;
+
+        for (const int n : nums)
+            mat[n % g][n]++;
+        for (const auto &mp : mat) {
+            int p = 0, dp0 = 1, dp1 = 0;
+            for (const auto [k, v] : mp) {
+                const int t = (1 << v) - 1;
+                dp0 += dp1;
+                dp1 = t * (p + g == k ? dp0 - dp1 : dp0);
+                p = k;
+            }
+            res *= dp0 + dp1;
+        }
+
+        return res - 1;
+    }
+};
diff --git a/README.md b/README.md
@@ -1156,6 +1156,7 @@ for solving problems.
 |  2592  |   Medium   | [Maximize Greatness of an Array](Problems/2592.cpp)                                                |
 |  2593  |   Medium   | [Find Score of an Array After Marking All Elements](Problems/2593.cpp)                             |
 |  2596  |   Medium   | [Check Knight Tour Configuration](Problems/2596.cpp)                                               |
+|  2597  |   Medium   | [The Number of Beautiful Subsets](Problems/2597.cpp)                                               |
 |  2606  |   Medium   | [Find the Substring With Maximum Cost](Problems/2606.cpp)                                          |
 |  2610  |   Medium   | [Convert an Array Into a 2D Array With Conditions](Problems/2610.cpp)                              |
 |  2616  |   Medium   | [Minimize the Maximum Difference of Pairs](Problems/2616.cpp)                                      |