Fastest execution || beats 96% users with java & C++, 100% users with typescript || Python3 || DP
Approach\nDynamic Programming\n\n# Complexity\n- Time complexity: O(nlogn)\n\n- Space complexity: O(n)\n\n# Explanation\n1. Frequency Map Initialization:\n\n- W
# Approach\nDynamic Programming\n\n# Complexity\n- Time complexity: O(nlogn)\n\n- Space complexity: O(n)\n\n# Explanation\n1. **Frequency Map Initialization:**\n\n- We use a Map<Integer, Map<Integer, Integer>> called freqMap to store frequency counts of elements based on their remainders when divided by k.\n2. **Populating Frequency Map:**\n\n- We iterate through the nums array.\n- For each number, we compute its remainder when divided by k and update the nested map to count occurrences of each number.\n3. **Processing Each Remainder Group:**\n\n- For each group of numbers sharing the same remainder, we use dynamic programming to calculate the number of valid subsets.\n- We sort the numbers in the group and initialize counts for the dynamic programming approach.\n4. **Dynamic Programming Approach:**\n\n- We iterate through the sorted numbers in reverse.\n- For each number, we compute:\n    - skip: the count of subsets excluding the current number.\n    - take: the count of subsets including the current number, adjusted by the number of occurrences and whether it can be paired with subsequent numbers.\n- We update the total count of subsets considering both including and excluding the current number.\n5. **Combining Results:**\n\n- Multiply the counts of valid subsets for each remainder group.\nSubtract 1 from the total to exclude the empty subset and return the result.\n\n\n---\n\n```java []\nimport java.util.*;\n\npublic class Solution {\n    public int beautifulSubsets(int[] nums, int k) {\n        int totCount = 1;\n        Map<Integer, Map<Integer, Integer>> freqMap = new HashMap<>();\n\n        // Calculate frequencies based on remainder\n        for (int num : nums) {\n            int remainder = num % k;\n            freqMap.putIfAbsent(remainder, new HashMap<>());\n            freqMap.get(remainder).put(num, freqMap.get(remainder).getOrDefault(num, 0) + 1);\n        }\n\n        // Iterate through each remainder group\n        for (Map<Integer, Integer> fr : freqMap.values()) {\n            int n = fr.size();\n            int currCount = 1;\n            int next1 = 1;\n            int next2 = 0;\n            List<Map.Entry<Integer, Integer>> subsets = new ArrayList<>(fr.entrySet());\n            subsets.sort(Map.Entry.comparingByKey());\n\n            // Calculate counts for each subset starting from the second last\n            for (int i = n - 1; i >= 0; i--) {\n                int skip = next1;\n\n                int take = (1 << subsets.get(i).getValue()) - 1;\n\n                if (i + 1 < n && subsets.get(i + 1).getKey() - subsets.get(i).getKey() == k) {\n                    take *= next2;\n                } else {\n                    take *= next1;\n                }\n\n                currCount = skip + take;\n                next2 = next1;\n                next1 = currCount;\n            }\n\n            totCount *= currCount;\n        }\n\n        return totCount - 1;\n    }\n}\n```\n```C++ []\n#include <vector>\n#include <unordered_map>\n#include <map>\n#include <algorithm>\n#include <cmath>\n\nusing namespace std;\n\nclass Solution {\npublic:\n    int beautifulSubsets(vector<int>& nums, int k) {\n        int totCount = 1;\n        unordered_map<int, map<int, int>> freqMap;\n\n        // Calculate frequencies based on remainder\n        for (int num : nums) {\n            int remainder = num % k;\n            freqMap[remainder][num]++;\n        }\n\n        // Iterate through each remainder group\n        for (auto& frPair : freqMap) {\n            map<int, int>& fr = frPair.second;\n            int n = fr.size();\n            int currCount = 1;\n            int next1 = 1;\n            int next2 = 0;\n            vector<pair<int, int>> subsets(fr.begin(), fr.end());\n\n            // Calculate counts for each subset starting from the second last\n            for (int i = n - 1; i >= 0; i--) {\n                int skip = next1;\n                int take = pow(2, subsets[i].second) - 1;\n\n                if (i + 1 < n && subsets[i + 1].first - subsets[i].first == k) {\n                    take *= next2;\n                } else {\n                    take *= next1;\n                }\n\n                currCount = skip + take;\n                next2 = next1;\n                next1 = currCount;\n            }\n\n            totCount *= currCount;\n        }\n\n        return totCount - 1;\n    }\n};\n```\n```python3 []\nclass Solution:\n    def beautifulSubsets(self, nums: List[int], difference: int) -> int:\n        tot_count = 1\n        freq_map = defaultdict(dict)\n\n        # Calculate frequencies based on remainder\n        for num in nums:\n            remainder = num % difference\n            freq_map[remainder][num] = freq_map[remainder].get(num, 0) + 1\n\n        # Iterate through each remainder group\n        for fr in freq_map.values():\n            n = len(fr)\n            curr_count = 1\n            next1 = 1\n            next2 = 0\n            subsets = sorted(fr.items())\n\n            # Calculate counts for each subset starting from the second last\n            for i in range(n - 1, -1, -1):\n                # Count of subsets skipping the current subset\n                skip = next1\n\n                # Count of subsets including the current subset\n                take = 2 ** subsets[i][1] - 1\n\n                # If next number has a \'difference\', calculate subsets; otherwise, move to next\n                if i + 1 < n and subsets[i + 1][0] - subsets[i][0] == difference:\n                    take *= next2\n                else:\n                    take *= next1\n                \n                # Store the current total count for the current subset\n                curr_count = skip + take  \n                next2, next1 = next1, curr_count\n\n            tot_count *= curr_count\n\n        return tot_count - 1\n```\n```Typescript []\n\nfunction beautifulSubsets(nums: number[], k: number): number {\n    let totCount = 1;\n    const freqMap: Map<number, Map<number, number>> = new Map();\n\n    // Calculate frequencies based on remainder\n    for (let num of nums) {\n        let remainder = num % k;\n        if (!freqMap.has(remainder)) {\n            freqMap.set(remainder, new Map());\n        }\n        const remainderMap = freqMap.get(remainder)!;\n        remainderMap.set(num, (remainderMap.get(num) || 0) + 1);\n    }\n\n    // Iterate through each remainder group\n    for (let fr of freqMap.values()) {\n        const subsets = Array.from(fr.entries()).sort((a, b) => a[0] - b[0]);\n        const n = subsets.length;\n        let currCount = 1;\n        let next1 = 1;\n        let next2 = 0;\n\n        // Calculate counts for each subset starting from the second last\n        for (let i = n - 1; i >= 0; i--) {\n            let skip = next1;\n\n            let take = (1 << subsets[i][1]) - 1;\n\n            if (i + 1 < n && subsets[i + 1][0] - subsets[i][0] === k) {\n                take *= next2;\n            } else {\n                take *= next1;\n            }\n\n            currCount = skip + take;\n            next2 = next1;\n            next1 = currCount;\n        }\n\n        totCount *= currCount;\n    }\n\n    return totCount - 1;\n}\n```
['Array', 'Dynamic Programming', 'C++', 'Java', 'TypeScript', 'Python3']