Number of subsets - CollegeStash

For a given list of integers and integer K, find the number of non-empty subsets S such that min(S) + max(S) <= K.

Example 1:

nums = [2, 4, 5, 7]
k = 8
Output: 5
Explanation: [2], [4], [2, 4], [2, 4, 5], [2, 5]

Code:

var nums = [2, 4, 5, 7];

var findNum = function(nums, k) {
  nums.sort((a, b) => a - b);
  var count = 0;
  var low = 0;
  var high = nums.length - 1;
  while (low <= high) {
    if (nums[low] + nums[high] > k) {
      high--;
    } else {
      // Total subsets for set of n =  2^n
      count += 1 << (high - low);
      low++;
    }
  }
  return count;
}

console.log(findNum(nums, 8));
// Runtime complexity O(nlogn)
// Output: 5

Demo

Related