✔💯 DAY 362 || [JAVA/C++/PYTHON] || 100% || EXPLAINED || INTUTION || TC 0(N)
\n\n# UPVOTE PLS\n\n# Intuition & Approach\n Describe your first thoughts on how to solve this problem. \n##### \u2022\tThe goal is to count the number of subse
\n![image.png](https://assets.leetcode.com/users/images/8c8c2221-8c9f-4638-8411-13758d56504b_1680025666.3824496.png)\n# UPVOTE PLS\n\n# Intuition & Approach\n<!-- Describe your first thoughts on how to solve this problem. -->\n##### \u2022\tThe goal is to count the number of subsets of an integer array nums that satisfy a certain condition. The condition is that for any two distinct elements a and b in a subset, the absolute difference |a-b| should be exactly equal to k.\n##### \u2022\tThe code works by first creating a HashMap called frequencyMap that maps each number in the array to its frequency. Then it loops through each number in frequencyMap, and for each number it checks if there is another number in the map that is k less than it. If there is not, then it skips to the next number.\n##### \u2022\tIf there is another number that is k less than the current number, then the code finds all other numbers that are k apart from each other, and creates a list of their frequencies. It then uses this list to calculate the number of subsets that satisfy the condition.\n##### \u2022\tThe calculation is done using two variables, subsetWithout and subsetWith. subsetWithout keeps track of the number of subsets that do not include any of the k apart numbers, while subsetWith keeps track of the number of subsets that include at least one of the k apart numbers. The final answer is the product of all the subsetWith and subsetWithout values for each set of k apart numbers, plus 1 to account for the empty subset.\n##### \u2022\tThe code then repeats this process for each number in the array, and multiplies the results together to get the final answer. The final answer is then subtracted by 1 to account for the empty subset.\n\n\n\n# Code\n```java []\n public int beautifulSubsets(int[] nums, int k) {\n        Map<Integer, Integer> frequencyMap = new HashMap<>();\n        for (int num: nums) {\n            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);\n        }\n        int result = 1;\n        for (Map.Entry<Integer, Integer> entry: frequencyMap.entrySet()) {\n            int key = entry.getKey();\n            if (!frequencyMap.containsKey(key - k)) {\n                if (!frequencyMap.containsKey(key + k)) {\n                    result *= (1 << frequencyMap.get(key));\n                    continue;\n                }\n                List<Integer> kDiffFrequencies = new ArrayList<>();\n                kDiffFrequencies.add(frequencyMap.get(key));\n                while (frequencyMap.containsKey(key + k)) {\n                    key += k;\n                    kDiffFrequencies.add(frequencyMap.get(key));\n                }\n                int subsetWithout = 0, subsetWith = 0;\n                for (int frequency: kDiffFrequencies) {\n                    subsetWithout = subsetWith + subsetWithout;\n                    subsetWith = ((1 << frequency) - 1) * ((subsetWithout - subsetWith) + 1);\n                }\n                result *= (subsetWith + subsetWithout + 1);\n            }\n        }\n        return result - 1;\n    }\n```\n```c++ []\n    int beautifulSubsets(vector<int>& nums, int k) {\n        unordered_map<int, int> frequencyMap;\n        for (int num : nums) {\n            frequencyMap[num]++;\n        }\n\n        int result = 1;\n        for (auto entry : frequencyMap) {\n            int key = entry.first;\n            if (!frequencyMap.count(key - k)) {\n                if (!frequencyMap.count(key + k)) {\n                    result *= (1 << frequencyMap[key]);\n                    continue;\n                }\n\n                vector<int> kDiffFrequencies;\n                kDiffFrequencies.push_back(frequencyMap[key]);\n                while (frequencyMap.count(key + k)) {\n                    key += k;\n                    kDiffFrequencies.push_back(frequencyMap[key]);\n                }\n\n                int subsetWithout = 0, subsetWith = 0;\n                for (int frequency : kDiffFrequencies) {\n                    subsetWithout = subsetWith + subsetWithout;\n                    subsetWith = ((1 << frequency) - 1) * ((subsetWithout - subsetWith) + 1);\n                }\n\n                result *= (subsetWith + subsetWithout + 1);\n            }\n        }\n\n        return result - 1;\n    }\n```\n```python []\n    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n        frequencyMap = {}\n        for num in nums:\n            frequencyMap[num] = frequencyMap.get(num, 0) + 1\n\n        result = 1\n        for key, value in frequencyMap.items():\n            if key - k not in frequencyMap:\n                if key + k not in frequencyMap:\n                    result *= (1 << frequencyMap[key])\n                    continue\n\n                kDiffFrequencies = [frequencyMap[key]]\n                while key + k in frequencyMap:\n                    key += k\n                    kDiffFrequencies.append(frequencyMap[key])\n\n                subsetWithout, subsetWith = 0, 0\n                for frequency in kDiffFrequencies:\n                    subsetWithout, subsetWith = subsetWith + subsetWithout, ((1 << frequency) - 1) * ((subsetWithout - subsetWith) + 1)\n\n                result *= (subsetWith + subsetWithout + 1)\n\n        return result - 1\n```\nMY LINKE : https://leetcode.com/problems/the-number-of-beautiful-subsets/solutions/3352572/day-362-java-c-python-100-explained-intution-tc-0-n/?orderBy=most_votes\n\n# Complexity\n\n##### \u2022\tTime complexity: \n##### \u2022\tThe function first creates a frequency map of the input array, which takes O(n) time, where n is the length of the input array. \n##### \u2022\tThe function then loops through each entry in the frequency map, which takes O(m) time, where m is the number of unique elements in the input array.\n##### \u2022\tFor each entry in the frequency map, the function checks if the value starts a chain of k difference values. \n##### \u2022\tThis takes O(1) time. If the value does start a chain, the function creates a list of the frequencies of the values in the chain, which takes O(l) time, where l is the length of the chain. \n##### \u2022\tThe function then loops through the frequencies in the list and calculates the number of beautiful subsets that can be formed using the values in the chain. This takes O(l) time. \n##### \u2022\tFinally, the function multiplies the total number of beautiful subsets by the result accumulated so far, which takes O(1) time. Therefore, the total time complexity of the function is O(n + m * (l + l)), which simplifies to O(n + ml). \n##### \u2022\tSpace complexity: The function creates a frequency map of the input array, which takes O(m) space, where m is the number of unique elements in the input array. The function creates a list of the frequencies of the values in the chain, which takes O(l) space, where l is the length of the chain. The function uses a constant amount of extra space for variables like result , key , and value . Therefore, the total space complexity of the function is O(m + l), where m is the number of unique elements in the input array and l is the length of the chain.\n\n# 2ND WAY \n\n#  Intuition & Approach\n\n##### \u2022\tThe problem asks us to find the number of beautiful subsets of the given array A , where a subset is beautiful if the absolute difference between any two elements in the subset is exactly k . \n##### \u2022\tThe intuition behind the algorithm is to use dynamic programming to count the number of beautiful subsets that end with each element of the array. \n##### \u2022\tWe can then sum up these counts to get the total number of beautiful subsets. To implement this approach, we first count the frequency of each element in the array using a HashMap . \n##### \u2022\tWe then define a recursive function dp(a) that takes an element a and returns a pair of values (dp0, dp1) , where dp0 is the number of beautiful subsets that end with a and do not include any element that is k units away from a , and dp1 is the number of beautiful subsets that end with a and include at least one element that is k units away from a . To compute dp(a) , \n##### \u2022\twe check if there is an element a-k in the count map. If there is, we recursively call dp(a-k) to get the values (dp0\', dp1\') for the element a-k . \n##### \u2022\tWe can then compute dp0 and dp1 as follows: dp0 = dp0\' + dp1\' : We can append a to any beautiful subset that ends with a-k and does not include any element that is k units away from a . dp1 = dp0\' * (2^count[a] - 1) : \n##### \u2022\tWe can append a to any beautiful subset that ends with a-k and includes at least one element that is k units away from a . \n##### \u2022\tThere are dp0\' such subsets, and for each subset, we can choose any subset of the count[a] elements that are k units away from a , except for the empty subset. If there is no element a-k in the count map, we set dp0 = 1 and dp1 = 2^count[a] - 1 , since the only beautiful subset that ends with a is the singleton set {a} . To avoid redundant calculations, we use memoization to store the values of dp(a) in a HashMap called memo . \n##### \u2022\tFinally, we sum up the values of dp0 and dp1 for all elements a in the count map that do not have an element a+k in the count map, and multiply them together to get the total number of beautiful subsets. \n##### \u2022\tWe subtract 1 from the result to exclude the empty subset. The time complexity of this algorithm is O(n log n), where n is the length of the input array, since we need to sort the array and perform O(log n) recursive calls for each element. \n##### \u2022\tThe space complexity is also O(n), since we need to store the count map and the memo map.\n\n\n```PYTHON []\nfrom collections import Counter\nfrom functools import reduce\nfrom operator import mul\n\nclass Solution:\n    def beautifulSubsets(self, A: List[int], k: int) -> int:\n        count = Counter(A)\n\n        @lru_cache(None)\n        def dp(a):\n            if a - k in count:\n                dp0, dp1 = dp(a - k)\n            else:\n                dp0, dp1 = 1, 0\n            return dp0 + dp1, dp0 * (2 ** count[a] - 1)\n\n        return reduce(mul, (sum(dp(a)) for a in count if a + k not in count)) - 1\n```\n```JAVA []\n\n class Solution {\n    public int beautifulSubsets(int[] A, int k) {\n        Map<Integer, Integer> count = new HashMap<Integer, Integer>();\n        for (int a : A) {\n            if (count.containsKey(a)) {\n                count.put(a, count.get(a) + 1);\n            } else {\n                count.put(a, 1);\n            }\n        }\n\n        final Map<Integer, Pair<Integer, Integer>> memo = new HashMap<Integer, Pair<Integer, Integer>>();\n        Function<Integer, Pair<Integer, Integer>> dp = new Function<Integer, Pair<Integer, Integer>>() {\n            public Pair<Integer, Integer> apply(Integer a) {\n                if (count.containsKey(a - k)) {\n                    Pair<Integer, Integer> p = memo.containsKey(a - k) ? memo.get(a - k) : apply(a - k);\n                    int dp0 = p.getKey() + p.getValue();\n                    int dp1 = p.getKey() * ((1 << count.get(a)) - 1);\n                    Pair<Integer, Integer> result = new Pair<Integer, Integer>(dp0, dp1);\n                    memo.put(a, result);\n                    return result;\n                } else {\n                    Pair<Integer, Integer> result = new Pair<Integer, Integer>(1, (1 << count.get(a)) - 1);\n                    memo.put(a, result);\n                    return result;\n                }\n            }\n        };\n\n        int result = 1;\n        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {\n            int a = entry.getKey();\n            int freq = entry.getValue();\n            if (!count.containsKey(a + k)) {\n                Pair<Integer, Integer> p = memo.containsKey(a) ? memo.get(a) : dp.apply(a);\n                result *= p.getKey() + p.getValue();\n            }\n        }\n\n        return result - 1;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int beautifulSubsets(vector<int>& A, int k) {\n        unordered_map<int, int> count;\n        for (int a : A) {\n            count[a]++;\n        }\n\n        function<pair<int, int>(int)> dp = [&](int a) {\n            if (count.count(a - k)) {\n                auto [dp0, dp1] = dp(a - k);\n                return make_pair(dp0 + dp1, dp0 * ((1 << count[a]) - 1));\n            } else {\n                return make_pair(1, (1 << count[a]) - 1);\n            }\n        };\n\n        int result = 1;\n        for (auto [a, freq] : count) {\n            if (!count.count(a + k)) {\n                auto [dp0, dp1] = dp(a);\n                result *= dp0 + dp1;\n            }\n        }\n\n        return result - 1;\n    }\n};\n```\n# DRY RUN \nhere\'s a dry run of the function for the input nums = [2,4,6], k = 2:\n##### \u2022\tCreate a frequency map of the input array:\n##### \u2022\tcount = {\n##### \u2022\t  2: 1,\n##### \u2022\t  4: 1,\n##### \u2022\t  6: 1,\n##### \u2022\t}\n##### \u2022\tDefine the recursive function dp:\n##### \u2022\tdp(a) = (dp0, dp1)\n##### \u2022 where dp0 is the number of beautiful subsets that end with a and do not include any element that is k units away from a, and dp1 is the number of beautiful subsets that end with a and include at least one element that is k units away from a.\n##### \u2022 If count contains a - k, then we recursively call dp(a - k) to get the values (dp0\', dp1\') for a - k, and compute dp0 and dp1 as follows:\n##### \u2022 dp0 = dp0\' + dp1\'    // append a to any beautiful subset that ends with a-k and does not include any element that is k units away from a\n##### \u2022 dp1 = dp0\' * ((1 << count[a]) - 1)    // append a to any beautiful subset that ends with a-k and includes at least one element that is k units away from a\n##### \u2022 If count does not contain a - k, then we set dp0 = 1 and dp1 = (1 << count[a]) - 1, since the only beautiful subset that ends with a is the singleton set {a}.\n##### \u2022\tInitialize the result to 1, and loop through each element a in count that does not have an element a + k in count. For each such element, call dp(a) to get the values (dp0, dp1), and multiply the result by dp0 + dp1.\n##### \u2022\tresult = 1\n##### \u2022\tfor a, freq in count:\n##### \u2022\t  if not count.contains(a + k):\n##### \u2022\t    dp0, dp1 = dp(a)\n##### \u2022\t    result *= dp0 + dp1\n##### \u2022\tSubtract 1 from the result to exclude the empty subset.\n##### \u2022\tresult -= 1\n##### \u2022\tReturn the result, which is 4 in this case, since there are 4 beautiful subsets of [2,4,6] with absolute difference k = 2: [2,4], [4,6], [2,4,6], and {} (empty subset).\n\n\n![BREUSELEE.webp](https://assets.leetcode.com/users/images/0b543619-3a1b-4ddc-a9c8-18a654bf3beb_1680027671.40263.webp)\n\n\n![meme2.png](https://assets.leetcode.com/users/images/9a8e78eb-e53b-4307-9f8a-bf70e512b8a0_1680025478.1222885.png)\n
['Python', 'C++', 'Java', 'Python3']