Formatted question description: https://leetcode.ca/all/1498.html
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^51 <= nums[i] <= 10^61 <= 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/
// 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/
// 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;
}
};
Java
class Solution {
public int numSubseq(int[] nums, int target) {
final int MODULO = 1000000007;
int length = nums.length;
Integer[] indices = new Integer[length];
for (int i = 0; i < length; i++)
indices[i] = i;
Arrays.sort(indices, new Comparator<Integer>() {
public int compare(Integer index1, Integer index2) {
if (nums[index1] != nums[index2])
return nums[index1] - nums[index2];
else
return index1 - index2;
}
});
int[] power2 = new int[length + 1];
power2[0] = 1;
for (int i = 1; i <= length; i++)
power2[i] = (power2[i - 1] * 2) % MODULO;
int count = 0;
int pointer = length - 1;
for (int i = 0; i < length; i++) {
pointer = Math.max(pointer, i);
while (pointer > i && nums[indices[pointer]] + nums[indices[i]] > target)
pointer--;
if (nums[indices[pointer]] + nums[indices[i]] <= target) {
int subLength = pointer - i;
count = (count + power2[subLength]) % MODULO;
}
}
return count;
}
}