LeetCode 1498: Number of Subsequences That Satisfy the Given Sum Condition
Problem Description
Explanation
To solve this problem, we can use a two-pointer approach along with sorting the input array. We will sort the array nums and then iterate through it using two pointers left and right. We will consider all possible subsequences where nums[left] + nums[right] <= target and count the number of valid subsequences. The total number of valid subsequences will be 2^(right-left) for each pair of left and right.
Time Complexity
The time complexity of this approach is O(N*logN) where N is the length of the input array nums.
Space Complexity
The space complexity is O(1) as we are not using any extra space other than a few variables.
Solutions
class Solution {
public int numSubseq(int[] nums, int target) {
int mod = 1000000007;
int n = nums.length;
Arrays.sort(nums);
int left = 0, right = n - 1;
long res = 0;
int[] pow = new int[n];
pow[0] = 1;
for (int i = 1; i < n; i++) {
pow[i] = (pow[i-1] * 2) % mod;
}
while (left <= right) {
if (nums[left] + nums[right] <= target) {
res = (res + pow[right - left]) % mod;
left++;
} else {
right--;
}
}
return (int) res;
}
}Loading editor...