leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

2597.cpp (616B)

      1 class Solution {
      2   public:
      3     int beautifulSubsets(const vector<int> &nums, const int g) const {
      4         const int n = size(nums);
      5         vector<map<int, int>> mat(g);
      6         int res = 1;
      7 
      8         for (const int n : nums)
      9             mat[n % g][n]++;
     10         for (const auto &mp : mat) {
     11             int p = 0, dp0 = 1, dp1 = 0;
     12             for (const auto [k, v] : mp) {
     13                 const int t = (1 << v) - 1;
     14                 dp0 += dp1;
     15                 dp1 = t * (p + g == k ? dp0 - dp1 : dp0);
     16                 p = k;
     17             }
     18             res *= dp0 + dp1;
     19         }
     20 
     21         return res - 1;
     22     }
     23 };