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 byk
. -
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 adefaultdict
from thecollections
module. The expressiong[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 ofm + 1
, wherem
is the number of elements in the current group.f[i]
will store the number of "k-Free" subsets possible with the firsti
elements of the group. -
Base Cases:
f[0]
is1
, representing the empty set, andf[1]
is2
. 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 thei-1
th and thei-2
th elements. Ifarr[i - 1] - arr[i - 2]
is equal tok
, we cannot have both elements in a subset, sof[i]
is the sum off[i - 1]
(excludingarr[i - 1]
) andf[i - 2]
(includingarr[i - 1]
and excludingarr[i - 2]
). Otherwise,f[i]
is twicef[i - 1]
, as we can freely choose to include or exclude thei-1
th element in each subset counted byf[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 ofans
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 EvaluatorExample 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 arrayf
with the base casef[0]=1
. We havef[1]=2
, representing the number of subsets when we consider up to the first element of this group. Since7-4 != k
, we use the relationf[i]=f[i-1]*2
, giving usf[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 withf[0] = 1
,f[1] = 2
. Forf[2]
, since5-2 != k
, we can double the previous count, resulting inf[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 arraynums
.
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 takesO(n * log n)
time wheren
is the total number of elements innums
. - The for loop iterates over each number in sorted
nums
array and performs operations of constant time complexity to fill the dictionaryg
. This step runs inO(n)
time. - For each mod group gathered in
g
, we calculate a dynamic programming solution which has a time complexity ofO(m)
wherem
is the length of that group ing
. - 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 takesO(n)
time. This step is repeated for each unique modulus (up tok
groups), leading to a complexity ofO(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
requiresO(n)
space. - The dictionary
g
which contains the elements ofnums
grouped by their modulusk
can also take up toO(n)
space in total. - The array
f
in the dynamic programming section is recreated for each group and is of sizem + 1
wherem
is the length of the current group being considered; this space would be reused for each group. The peak space taken byf
is the size of the largest group, which is at mostn
.
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.
You are given an array of intervals where intervals[i] = [start_i, end_i]
represent the start and end of the ith
interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!