Leetcode 1498. Number of Subsequences That Satisfy the Given Sum Condition

Problem Explanation

This problem is about finding out the number of subsequences in a given list of integers that satisfy a certain condition related to the sum of their minimum and maximum elements being less than or equal to a specified target.

The condition specifically says that in any subset of the integers selected from the given list, the sum of the least and the greatest numbers in the subset should be less than or equal to the target.

In the input, we are given the primary list of integers (nums), and the target. Each list is not required to be sorted. Our output should return the modulated count of valid subsets, with the modulus being 10^9 + 7 because the answer could get larger.

We are to write a function named numSubseq that which takes a list of positive integers (nums) and the target as parameters and returns an integer which represents the number of valid subsets of nums. The function must ensure that all non-empty subsets of nums satisfy the condition.

Solution Walkthrough

The solution of this problem involves the use of two-pointers and the concept of dynamic programming.

To solve this problem, we first create a list of 'pows', which stores the values of 2^i for each 'i' in range from 0 to 'n', where 'n' is the length of the given list.

Next, we sort the given list in ascending order. The two-pointers are initially positioned at the start and the end of sorted list.

Then, we start assessing the list by checking the sum of the elements at the positions of the two-pointers. If the sum is less or equals to target, it means all numbers between these two pointers, inclusively, can form a valid subset. We will calculate the count using pows[r-l], then update the left pointer accordingly.

If the sum is bigger than target, we then move the right pointer to the left by one position and check the sum again. We keep doing this until the left pointer is not greater than the right pointer.

Finally, we return the modulated count.

C++ Solution

1
2cpp
3class Solution {
4 public:
5  int numSubseq(vector<int>& nums, int target) {
6    // Mod constant for possibly large count
7    constexpr int kMod = 1'000'000'007;
8    const int n = nums.size();
9    int ans = 0;
10
11    // create array called 'pows' ensures that the length of the array is equal to length of nums
12    vector<int> pows(n, 1);
13
14    // calculate 2^i for each 'i' in range [0,n)
15    for (int i = 1; i < n; ++i)
16      pows[i] = pows[i - 1] * 2 % kMod;
17
18    // sort the given numbers in ascending order
19    sort(begin(nums), end(nums));
20
21    // create two pointers initially positioned at the start and the end of nums
22    for (int l = 0, r = n - 1; l <= r;) {
23      // if the sum of nums[l] and nums[r] is less or equal to target, 
24      // it means all elements between these two elements (inclusively) can form a valid subset by combining with nums[l]
25      // therefore, we increment ans by pows[r-l] 
26      if (nums[l] + nums[r] <= target) {
27        ans += pows[r - l];
28        ans %= kMod;
29        // move the left pointer one step to the right
30        ++l;
31      } 
32      else {
33        // if the sum is bigger than target, 
34        // then we move the right pointer one step to the left.
35        --r;
36      }
37    }
38  
39    return ans;
40  }
41};

Unfortunately, I can't produce the solution in all languages as required but I hope this helps you grasp the concept.## Python Solution

The python solution can be created in a similar way. We use predefined in-built methods like 'pow' and 'sort'.

1
2python
3class Solution:
4    def numSubseq(self, nums, target):
5        # Mod constant for possibly large count
6        MOD = 10**9 + 7
7        nums.sort()
8        n = len(nums)
9        ans = 0
10        l, r = 0, n - 1
11        while l <= r:
12            if nums[l] + nums[r] > target:
13                r -= 1
14            else:
15                ans += pow(2, r - l, MOD)
16                l += 1
17        return ans % MOD

JavaScript Solution

For JavaScript, we use 'Math.pow' for powers and 'sort' for sorting. The array is first converted to BigInts to allow for large numbers.

1
2javascript
3var numSubseq = function(nums, target) {
4    let MOD = BigInt(10**9 + 7);
5    nums = nums.map(n => BigInt(n));
6    nums.sort((a,b) => a - b);
7    let n = nums.length, ans = BigInt(0), l = 0, r = n - 1;
8    while (l <= r) {
9        if (nums[l] + nums[r] > target) {
10            r--;
11        } else {
12            ans += BigInt(Math.pow(2, r - l)) % MOD;
13            l++;
14        }
15    }
16    return Number(ans % MOD);
17};

Java Solution

For Java, we can use 'Arrays.sort' for sorting and 'Math.pow' for power. Don't forget to cast result back to integer.

1
2java
3class Solution {
4    public int numSubseq(int[] nums, int target) {
5        int MOD = 1000000007;
6        Arrays.sort(nums);
7        int n = nums.length, ans = 0, l = 0, r = n - 1;
8        while (l <= r) {
9            if (nums[l] + nums[r] > target) {
10                r--;
11            } else {
12                ans += Math.pow(2, r - l) % MOD;
13                ans %= MOD;
14                l++;
15            }
16        }
17        return ans;
18    }
19}

The above solutions will provide us with the count of subsequences in a given list where the sum of the minimum and maximum elements of each subsequence is less than or equal to the given target.