diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /num_beautiful_subset.py | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'num_beautiful_subset.py')
-rw-r--r-- | num_beautiful_subset.py | 40 |
1 files changed, 40 insertions, 0 deletions
diff --git a/num_beautiful_subset.py b/num_beautiful_subset.py new file mode 100644 index 0000000..7b1a9a0 --- /dev/null +++ b/num_beautiful_subset.py @@ -0,0 +1,40 @@ +# 2597. The Number of Beautiful Subsets +import collections + +""" +given an array 'nums' of positive integers and a positive integer 'k'. a +subset of 'nums' is beautiful if it does not contain integers with an +absolute difference equal to 'k'. return the number of non empty beautiful +subsets of the array 'nums'. a subset of 'nums' is an array that can be +obtained by deleting some elements from 'nums'. two subsets are different iff +the chosen indices to delete are different. +""" + + +class Solution(object): + def beautifulSubsets(self, nums, k): + """ + :type nums: List[int] + :type k: int + :rtype: int + """ + ans = 1 + freq = collections.defaultdict(collections.Counter) + for i in nums: + freq[i % k][i] += 1 + for i in freq.values(): + prev_num, curr, prev1, prev2 = -k, 1, 1, 0 + for n in sorted(i): + skip = prev1 + take = (2 ** i[n] - 1) * (prev2 if n - prev_num == k else prev1) + curr = skip + take + prev2, prev1 = prev1, curr + prev_num = n + ans *= curr + return ans - 1 + + +if __name__ == "__main__": + obj = Solution() + print(obj.beautifulSubsets(nums=[2, 4, 6], k=2)) + print(obj.beautifulSubsets(nums=[1], k=1)) |