1498

1498. Number of Subsequences That Satisfy the Given Sum Condition (Medium)

Given an array of integers nums and an integer target.

Return the number of non-empty subsequences of nums such that the sum of the minimum and maximum element on it is less or equal than target.

Since the answer may be too large, return it modulo 10^9 + 7.

 

Example 1:

Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

Example 2:

Input: nums = [3,3,6,8], target = 10
Output: 6
Explanation: There are 6 subsequences that satisfy the condition. (nums can have repeated numbers).
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]

Example 3:

Input: nums = [2,3,3,4,6,7], target = 12
Output: 61
Explanation: There are 63 non-empty subsequences, two of them don't satisfy the condition ([6,7], [7]).
Number of valid subsequences (63 - 2 = 61).

Example 4:

Input: nums = [5,2,4,1,7,6,8], target = 16
Output: 127
Explanation: All non-empty subset satisfy the condition (2^7 - 1) = 127

 

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6
• 1 <= target <= 10^6

Related Topics:
Sort, Sliding Window

Solution 1. Two pointers

Consider input nums = [3,5,6,7], target = 9.

For 3, we can find the maximum number we can use which is 6. So we get a subarray [3,5,6]. Then how many subsequences starting with this 3 we can form using this subarray? It should be 2^(len - 1) = 2^2 = 4 because out of [5, 6], we just can choose to pick zero, one or two of them.

Then we consider the next element 5, and the right bound should only decrease so that we can still sum up to 9. So we can use two pointers, i scanning elements from left to right, and j starting from N - 1 and scanning leftwards to find the maximum right boundary.

// OJ: https://leetcode.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
    int numSubseq(vector<int>& A, int target) {
        sort(begin(A), end(A));
        int N = A.size(), ans = 0, mod = 1e9 + 7;
        vector<int> p(N, 1);
        for (int i = 1; i < N; ++i) p[i] = p[i - 1] * 2 % mod;
        for (int i = 0, j = N - 1; i <= j; ++i) {
            while (i <= j && A[i] + A[j] > target) --j;
            if (i > j) break;
            ans = (ans + p[j - i]) % mod;
        }
        return ans;
    }
};

Or use fast pow.

// OJ: https://leetcode.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
int modpow(int base, int exp, int mod) {
    base %= mod;
    int ans = 1;
    for (; exp > 0; exp >>= 1, base = (long)base * base % mod) {
        if (exp & 1) ans = ((long)ans * base) % mod;
    }
    return ans;
}
class Solution {
public:
    int numSubseq(vector<int>& A, int target) {
        sort(begin(A), end(A));
        int N = A.size(), ans = 0, mod = 1e9 + 7;
        for (int i = 0, j = N - 1; i <= j; ++i) {
            while (i <= j && A[i] + A[j] > target) --j;
            if (i > j) break;
            ans = (ans + modpow(2, j - i, mod)) % mod;
        }
        return ans;
    }
};