Skip to Content

Count the number of K Free Subsets

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

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 7 days ago

Related Problems

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

Return the maximum coins you can collect by bursting the balloons wisely.