2638. Count the Number of K-Free Subsets

Problem Description

In this problem, you're given an integer array nums, with distinct elements, and an integer k. Your task is to count the number of subsets of nums that are "k-Free." A subset is "k-Free" if no two elements in the subset have an absolute difference equal to k. It's important to remember that a subset can be any collection of elements from the array, including no elements at all, which means the empty set is always a "k-Free" subset.

Intuition

To solve this problem, we should start by understanding that we're looking for subsets where no two elements differ by k. Since the elements of nums are distinct, we can sort nums and group them by their remainder when divided by k. Each of these groups will contain elements that differ by, at a minimum, k from elements of other groups, meaning the absolute difference of k can only occur within the same group.

After the grouping, we can separate the problem into smaller subproblems: counting "k-Free" subsets within each group, independent of the others. We tackle this with dynamic programming, where f[i] will represent the number of "k-Free" subsets we can form using the first i elements of a group. The base cases are f[0] = 1, since there's only one empty subset of zero elements, and f[1] = 2, which represents the two subsets of a single-element group: the empty set and the set containing that element.

When we have at least two elements (i.e., i >= 2), we check if the absolute difference between the last two elements being considered is k. If it is, we can't include both of them in a "k-Free" subset. Hence, the number of "k-Free" subsets involving these two elements is the same as f[i - 1] + f[i - 2]: either we include the last element (and count subsets not including the previous one), or we don't (counting subsets up to the previous one). If the difference isn't k, then including the last element doesn't restrict us in any way, so we have f[i] = f[i - 1] * 2, as each existing subset can either include or exclude the last element, effectively doubling the count.

Once we have the count for each group, we multiply the counts together to get the total number of "k-Free" subsets, which gives us our answer.

Learn more about Dynamic Programming and Sorting patterns.

Solution Approach

The solution to this problem employs both sorting and dynamic programming, alongside additional data structures, to manage and compute the required counts of "k-Free" subsets.

Sorting: We begin by sorting the array nums to organize elements in ascending order. This allows us to easily group elements by their remainders when divided by k.
Grouping Elements: After sorting, the array elements are grouped based on their remainder modulo k. This is done using a dictionary where the key is the remainder and the value is a list of elements with that remainder. In Python, this is realized using a defaultdict from the collections module. The expression g[x % k].append(x) populates our groups.
Dynamic Programming: For each group of elements (with the same remainder), we use a dynamic programming approach to count the subsets. We initialize an array f with a length of m + 1, where m is the number of elements in the current group. f[i] will store the number of "k-Free" subsets possible with the first i elements of the group.
Base Cases: f[0] is 1, representing the empty set, and f[1] is 2. The latter represents the subsets possible with one element: one subset is the empty set, and another is the set containing just that one element.
Recurrence Relation: For i >= 2, we have a decision based on the difference between the i-1th and the i-2th elements. If arr[i - 1] - arr[i - 2] is equal to k, we cannot have both elements in a subset, so f[i] is the sum of f[i - 1] (excluding arr[i - 1]) and f[i - 2] (including arr[i - 1] and excluding arr[i - 2]). Otherwise, f[i] is twice f[i - 1], as we can freely choose to include or exclude the i-1th element in each subset counted by f[i - 1].
Final Computation: After computing the number of subsets for each group, the variable ans is used to hold the cumulative product of subset counts from each group. The final result is the value of ans after all groups have been processed.

Using this approach, we efficiently compute the count of "k-Free" subsets without having to examine each subset of nums individually. The dynamic programming aspect drastically reduces the complexity by breaking the problem down into manageable states for which the solution can be constructed iteratively.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take a small example to illustrate the solution approach. Consider the integer array nums = [1, 2, 4, 5, 7], and let k = 3. We want to count the number of "k-Free" subsets, where no two elements have an absolute difference of 3.

Sorting: First, we sort the array nums, but since our array is already sorted, we can move to the next step.
Grouping Elements: Next, we group elements based on their remainder when divided by k. The remainders and their groups will look like this:
- Remainder 0: [4, 7] (since 4%3=1 and 7%3=1)
- Remainder 1: [1]
- Remainder 2: [2, 5]
Each of these groups can be used to form "k-Free" subsets independently.
Dynamic Programming:
- For the group with remainder 0 ([4, 7]), we start with our dynamic programming array f with the base case f[0]=1. We have f[1]=2, representing the number of subsets when we consider up to the first element of this group. Since 7-4 != k, we use the relation f[i]=f[i-1]*2, giving us f[2] = f[1]*2 = 4. Thus, there are 4 subsets possible with elements [4, 7].
- For the group with remainder 1 ([1]), there are only two possible subsets (f[1] = 2): the empty set and the set [1].
- For the group with remainder 2 ([2, 5]), we start similarly with f[0] = 1, f[1] = 2. For f[2], since 5-2 != k, we can double the previous count, resulting in f[2] = f[1]*2 = 4.
Final Computation: We multiply the counts of each group's "k-Free" subsets to get the overall count. Multiplying the counts from each group together, we have 4 * 2 * 4 = 32. There are 32 "k-Free" subsets in the array nums.

By following these steps, we've demonstrated the method to find the number of "k-Free" subsets efficiently using dynamic programming without checking each possible subset explicitly.

Solution Implementation

1from collections import defaultdict
2
3class Solution:
4    def count_the_num_of_k_free_subsets(self, nums: List[int], k: int) -> int:
5        # Sort the numbers in ascending order
6        nums.sort()
7      
8        # Group numbers by their remainder when divided by k
9        remainder_groups = defaultdict(list)
10        for num in nums:
11            remainder_groups[num % k].append(num)
12      
13        # Initialize answer as 1
14        ans = 1
15      
16        # Loop through each group of numbers with the same remainder
17        for group in remainder_groups.values():
18            group_size = len(group)
19            # The dp array holds the count of k-free subsets up to the current index
20            dp = [0] * (group_size + 1)
21            dp[0] = 1  # One way to create a subset including no elements
22            dp[1] = 2  # Two ways to create a subset including the first element
23          
24            # Calculate the number of k-free subsets for the current group
25            for i in range(2, group_size + 1):
26                # If the difference between current and previous is k, we may merge the last two sets
27                if group[i - 1] - group[i - 2] == k:
28                    dp[i] = dp[i - 1] + dp[i - 2]
29                else:
30                    # Otherwise, we can either include or exclude the current number
31                    dp[i] = dp[i - 1] * 2
32          
33            # Multiply the result by the number of k-free subsets for the current group
34            ans *= dp[group_size]
35      
36        # Return the total number of k-free subsets
37        return ans
38

1class Solution {
2    public long countTheNumOfKFreeSubsets(int[] nums, int k) {
3        // Sort the input array.
4        Arrays.sort(nums);
5        // Group numbers in the array by their modulus k.
6        Map<Integer, List<Integer>> modulusGroups = new HashMap<>();
7        for (int num : nums) {
8            modulusGroups.computeIfAbsent(num % k, x -> new ArrayList<>()).add(num);
9        }
10        // Initialize answer to 1 since we will multiply the counts.
11        long answer = 1;
12        // Iterate through each group formed by the modulus operation.
13        for (List<Integer> group : modulusGroups.values()) {
14            int size = group.size();
15            // Dynamic programming array to hold the count of k-free subsets
16            long[] dp = new long[size + 1];
17            dp[0] = 1; // Base case: One way to form an empty subset.
18            dp[1] = 2; // Base case: Either include the first element or not.
19            // Fill up the dp array with the count of k-free subsets for each size.
20            for (int i = 2; i <= size; ++i) {
21                // Check if current and previous elements are k apart
22                if (group.get(i - 1) - group.get(i - 2) == k) {
23                    // If yes, we can form new subsets by adding the current element to subsets ending at i - 2
24                    dp[i] = dp[i - 1] + dp[i - 2];
25                } else {
26                    // If not, subsets can either include or not include the current element
27                    dp[i] = dp[i - 1] * 2;
28                }
29            }
30            // Multiply the total answer with the count of k-free subsets of current size.
31            answer *= dp[size];
32        }
33        // Return the final count of k-free subsets as the answer.
34        return answer;
35    }
36}
37

1#include <vector>
2#include <unordered_map>
3#include <algorithm>
4
5class Solution {
6public:
7    long long countTheNumOfKFreeSubsets(vector<int>& nums, int k) {
8        // Sort the input array.
9        sort(nums.begin(), nums.end());
10
11        // Create a map to categorize numbers by their modulo with k.
12        unordered_map<int, vector<int>> groupsByModulo;
13        for (int num : nums) {
14            groupsByModulo[num % k].push_back(num);
15        }
16
17        long long answer = 1; // Initialize the answer with 1 for multiplication.
18      
19        // Iterate through each group categorized by modulo with k.
20        for (auto& [modulo, group] : groupsByModulo) {
21            int groupSize = group.size();
22          
23            // Create a dynamic programming array to store intermediate results.
24            vector<long long> dp(groupSize + 1);
25            dp[0] = 1; // Base case: There's 1 way to make a subset with 0 elements.
26            dp[1] = 2; // If there's 1 element, we can either include or exclude it.
27
28            // Fill in the dynamic programming array.
29            for (int i = 2; i <= groupSize; ++i) {
30                // If the difference between two consecutive numbers is k, we have additional case to consider.
31                if (group[i - 1] - group[i - 2] == k) {
32                    // We can either add the current element in a new subset or add it to a subset without the previous element.
33                    dp[i] = dp[i - 1] + dp[i - 2];
34                } else {
35                    // Otherwise, we can choose to include or exclude the current element for each subset.
36                    dp[i] = dp[i - 1] * 2;
37                }
38            }
39
40            // Multiply the answer by the number of ways to make subsets for this group.
41            answer *= dp[groupSize];
42        }
43      
44        // Return the final answer.
45        return answer;
46    }
47};
48

1function countTheNumOfKFreeSubsets(nums: number[], k: number): number {
2    // Sort the array in non-decreasing order
3    nums.sort((a, b) => a - b);
4  
5    // Create a map to group numbers by their modulo k value
6    const moduloGroups: Map<number, number[]> = new Map();
7
8    // Populate the moduloGroups map
9    for (const num of nums) {
10        const modulo = num % k;
11        if (!moduloGroups.has(modulo)) {
12            moduloGroups.set(modulo, []);
13        }
14        moduloGroups.get(modulo)!.push(num);
15    }
16
17    // Initialize answer to 1 as a starting multiplication identity
18    let answer: number = 1;
19  
20    // Iterate over each group in the map
21    for (const groupArray of moduloGroups.values()) {
22        const groupSize = groupArray.length;
23      
24        // Initialize dynamic programming array with base cases
25        const subsetCounts: number[] = new Array(groupSize + 1).fill(1);
26        subsetCounts[1] = 2; // 2 ways for a single number: include or exclude
27      
28        // Calculate the number of K-free subsets for the group
29        for (let i = 2; i <= groupSize; ++i) {
30            // If the difference between consecutive elements is exactly k
31            if (groupArray[i - 1] - groupArray[i - 2] === k) {
32                subsetCounts[i] = subsetCounts[i - 1] + subsetCounts[i - 2];
33            } else {
34                // Else, the number of subsets is double of the previous
35                subsetCounts[i] = subsetCounts[i - 1] * 2;
36            }
37        }
38      
39        // Update answer by multiplying by the number of subsets for this group
40        answer *= subsetCounts[groupSize];
41    }
42
43    // Return the total number of K-free subsets
44    return answer;
45}
46

Time and Space Complexity

Time Complexity

The time complexity of the provided code is as follows:

First, sorting the nums array which takes O(n * log n) time where n is the total number of elements in nums.
The for loop iterates over each number in sorted nums array and performs operations of constant time complexity to fill the dictionary g. This step runs in O(n) time.
For each mod group gathered in g, we calculate a dynamic programming solution which has a time complexity of O(m) where m is the length of that group in g.
Assuming that the elements are distributed uniformly across the groups, in the worst case, the size of each group could be close to n. Hence each dp calculation for a group in worst case takes O(n) time. This step is repeated for each unique modulus (up to k groups), leading to a complexity of O(k * n) in the worst case.
Multiplying the results of dynamic programming solutions for each group is constant for each iteration, adding only a negligible amount of time to the overall complexity.

Given the typical constraint where k is much smaller than n, the O(n * log n) term from sorting dominates the overall time complexity. Therefore, the reference answer's claim of O(n * log n) time complexity holds.

Space Complexity

The space complexity of the provided code is as follows:

The sorted array nums requires O(n) space.
The dictionary g which contains the elements of nums grouped by their modulus k can also take up to O(n) space in total.
The array f in the dynamic programming section is recreated for each group and is of size m + 1 where m is the length of the current group being considered; this space would be reused for each group. The peak space taken by f is the size of the largest group, which is at most n.

Combining these two we see the space complexity is O(n) to account for the storage of sorted nums and the dictionary g with all its lists, matching the reference answer's claim of O(n) space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which type of traversal does breadth first search do?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don’t know