Count the number of K Free Subsets

Home | Coding Interviews | Dynamic Programming | Count the number of K Free Subsets

Dynamic Programming Hard Video Python Java

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.


//Solution 1
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;
    }
}

//Solution 2
class Solution {
  public long countTheNumOfKFreeSubsets(int[] nums, int k) {
    Map<Integer, Set<Integer>> modToSubset = new HashMap<>();

    for (final int num : nums) {
      modToSubset.putIfAbsent(num % k, new TreeSet<>());
      modToSubset.get(num % k).add(num);
    }

    int prevNum = -k;
    long skip = 0;
    long pick = 0;

    for (Set<Integer> subset : modToSubset.values())
      for (final int num : subset) {
        final long cacheSkip = skip;
        skip += pick;
        pick = 1 + cacheSkip + (num - prevNum == k ? 0 : pick);
        prevNum = num;
      }

    return 1 + skip + pick;
  }
}

class Solution:
  def countTheNumOfKFreeSubsets(self, nums: list[int], k: int) -> int:
    modToSubset = collections.defaultdict(set)

    for num in nums:
      modToSubset[num % k].add(num)

    prevNum = -k
    skip = 0
    pick = 0

    for subset in modToSubset.values():
      for num in sorted(subset):
        skip, pick = (skip + pick,
                      1 + skip + (0 if num - prevNum == k else pick))
        prevNum = num

    return 1 + skip + pick

The solution to the k-Free subset problem revolves around breaking the array into groups based on their remainders when divided by k. This works because elements in different groups cannot have an absolute difference equal to k, allowing subsets to be formed freely within each group. By sorting the array and assigning each element to a group based on its remainder, we avoid conflicts between numbers that could violate the k-Free condition.

Once the array is grouped, the problem reduces to calculating the number of valid subsets within each group. The key is to decide for each element whether to include it in the subset based on whether its difference from the previous element is equal to k. By keeping track of two possibilities—whether to skip or pick an element—we can efficiently calculate the total number of valid subsets for the entire array by multiplying the results from each group.

Posted by grwgreg 3 months ago

Count the number of K Free Subsets

Related Problems