LeetCode 2638. Count the Number of K-Free Subsets Solution in Java, C++, Python & More | Explanation + Code

Description

You are given an integer array nums, which contains distinct elements and an integer k.

A subset is called a k-Free subset if it contains no two elements with an absolute difference equal to k. Notice that the empty set is a k-Free subset.

Return the number of k-Free subsets of nums.

A subset of an array is a selection of elements (possibly none) of the array.

 

Example 1:

Input: nums = [5,4,6], k = 1
Output: 5
Explanation: There are 5 valid subsets: {}, {5}, {4}, {6} and {4, 6}.

Example 2:

Input: nums = [2,3,5,8], k = 5
Output: 12
Explanation: There are 12 valid subsets: {}, {2}, {3}, {5}, {8}, {2, 3}, {2, 3, 5}, {2, 5}, {2, 5, 8}, {2, 8}, {3, 5} and {5, 8}.

Example 3:

Input: nums = [10,5,9,11], k = 20
Output: 16
Explanation: All subsets are valid. Since the total count of subsets is 24 = 16, so the answer is 16. 

 

Constraints:

• 1 <= nums.length <= 50
• 1 <= nums[i] <= 1000
• 1 <= k <= 1000

Solutions

Solution 1: Grouping + Dynamic Programming

First, sort the array nums in ascending order, and then group the elements in the array according to the remainder modulo k, that is, the elements nums[i] \bmod k with the same remainder are in the same group. Then for any two elements in different groups, their absolute difference is not equal to k. Therefore, we can obtain the number of subsets in each group, and then multiply the number of subsets in each group to obtain the answer.

For each group arr, we can use dynamic programming to obtain the number of subsets. Let f[i] denote the number of subsets of the first i elements, and initially f[0] = 1, and f[1]=2. When i ≥ 2, if arr[i-1]-arr[i-2]=k, if we choose arr[i-1], then f[i]=f[i-2]; If we do not choose arr[i-1], then f[i]=f[i-1]. Therefore, when arr[i-1]-arr[i-2]=k, we have f[i]=f[i-1]+f[i-2]; otherwise f[i] = f[i - 1] × 2. The number of subsets of this group is f[m], where m is the length of the array arr.

Finally, we multiply the number of subsets of each group to obtain the answer.

The time complexity is O(n × log n) and the space complexity is O(n), where n is the length of the array nums.

PythonJavaC++GoTypeScript

class Solution: def countTheNumOfKFreeSubsets(self, nums: List[int], k: int) -> int: nums.sort() g = defaultdict(list) for x in nums: g[x % k].append(x) ans = 1 for arr in g.values(): m = len(arr) f = [0] * (m + 1) f[0] = 1 f[1] = 2 for i in range(2, m + 1): if arr[i - 1] - arr[i - 2] == k: f[i] = f[i - 1] + f[i - 2] else: f[i] = f[i - 1] * 2 ans *= f[m] return ans(code-box)

class Solution { public long countTheNumOfKFreeSubsets(int[] nums, int k) { Arrays.sort(nums); Map<Integer, List<Integer>> g = new HashMap<>(); for (int i = 0; i < nums.length; ++i) { g.computeIfAbsent(nums[i] % k, x -> new ArrayList<>()).add(nums[i]); } long ans = 1; for (var arr : g.values()) { int m = arr.size(); long[] f = new long[m + 1]; f[0] = 1; f[1] = 2; for (int i = 2; i <= m; ++i) { if (arr.get(i - 1) - arr.get(i - 2) == k) { f[i] = f[i - 1] + f[i - 2]; } else { f[i] = f[i - 1] * 2; } } ans *= f[m]; } return ans; } }(code-box)

class Solution { public: long long countTheNumOfKFreeSubsets(vector<int>& nums, int k) { sort(nums.begin(), nums.end()); unordered_map<int, vector<int>> g; for (int i = 0; i < nums.size(); ++i) { g[nums[i] % k].push_back(nums[i]); } long long ans = 1; for (auto& [_, arr] : g) { int m = arr.size(); long long f[m + 1]; f[0] = 1; f[1] = 2; for (int i = 2; i <= m; ++i) { if (arr[i - 1] - arr[i - 2] == k) { f[i] = f[i - 1] + f[i - 2]; } else { f[i] = f[i - 1] * 2; } } ans *= f[m]; } return ans; } };(code-box)

func countTheNumOfKFreeSubsets(nums []int, k int) int64 { sort.Ints(nums) g := map[int][]int{} for _, x := range nums { g[x%k] = append(g[x%k], x) } ans := int64(1) for _, arr := range g { m := len(arr) f := make([]int64, m+1) f[0] = 1 f[1] = 2 for i := 2; i <= m; i++ { if arr[i-1]-arr[i-2] == k { f[i] = f[i-1] + f[i-2] } else { f[i] = f[i-1] * 2 } } ans *= f[m] } return ans }(code-box)

function countTheNumOfKFreeSubsets(nums: number[], k: number): number { nums.sort((a, b) => a - b); const g: Map<number, number[]> = new Map(); for (const x of nums) { const y = x % k; if (!g.has(y)) { g.set(y, []); } g.get(y)!.push(x); } let ans: number = 1; for (const [_, arr] of g) { const m = arr.length; const f: number[] = new Array(m + 1).fill(1); f[1] = 2; for (let i = 2; i <= m; ++i) { if (arr[i - 1] - arr[i - 2] === k) { f[i] = f[i - 1] + f[i - 2]; } else { f[i] = f[i - 1] * 2; } } ans *= f[m]; } return ans; }(code-box)