Sponsored
Sponsored
This approach involves sorting the array and then using a two pointers method to determine valid subsequences. We focus on the potential minimum and maximum values in a subsequence.
After sorting, use two pointers, one starting from the beginning of the array (for the minimum) and the other from the end (for the maximum). For each minimum, the number of valid subsequences is determined by how many elements from the minimum can pair with elements from the maximum such that their sum is less than or equal to the target. The number of subsequences can be calculated using the binary exponentiation of 2 with the distance between the two pointers.
Time Complexity: O(n log n), due to sorting the array.
Space Complexity: O(1), or O(n) if considering the space used by sorting.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <cmath>
5
6using namespace std;
7
8#define MOD 1000000007
9
10long power(int x, int y, int p) {
11 long res = 1;
12 x = x % p;
13 while (y > 0) {
14 if (y & 1)
15 res = (res * x) % p;
y = y >> 1;
x = (x * x) % p;
}
return res;
}
int numSubseq(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
long result = 0;
int left = 0, right = nums.size() - 1;
while (left <= right) {
if (nums[left] + nums[right] <= target) {
result = (result + power(2, right - left, MOD)) % MOD;
left++;
} else {
right--;
}
}
return (int)result;
}
int main() {
vector<int> nums = {3, 5, 6, 7};
int target = 9;
cout << numSubseq(nums, target) << endl;
return 0;
}The C++ solution uses the vector library to handle the input array, and the sort function sorts this array. Like the C solution, it has a power function for calculating exponentiation. The main logic within numSubseq finds the number of valid subsequences using two pointers to iterate through the sorted list and update the result based on valid minimum and maximum combinations.
This approach involves dynamic programming where pre-computed powers of 2 are used to calculate valid subsequences. Using arrays to store results dynamically avoids repetitive calculations and exploits binary indexing for faster computation on potential subsets.
The idea is to create a precompute power array of size n to store power values of 2 up to n. Iterating with this precompute allows identifying valid subsequences without recalculating powers each iteration, enhancing efficiency especially for extremely large arrays.
Time Complexity: O(n log n) for sorting. The DP preparation step is O(n).
Space Complexity: O(n) due to the power array creation.
1import java.util.Arrays;
2
3public class Solution {
4 private static final int MOD = 1000000007;
5
6 public int numSubseq(int[] nums, int target) {
7 Arrays.sort(nums);
8 int n = nums.length;
9 long[] power_2 = new long[n];
10 power_2[0] = 1;
11 for (int i = 1; i < n; i++) {
12 power_2[i] = (power_2[i - 1] * 2) % MOD;
13 }
14
15 long result = 0;
16 int left = 0, right = nums.length - 1;
17
18 while (left <= right) {
19 if (nums[left] + nums[right] <= target) {
20 result = (result + power_2[right - left]) % MOD;
21 left++;
22 } else {
23 right--;
24 }
25 }
26 return (int) result;
27 }
28
29 public static void main(String[] args) {
30 Solution solution = new Solution();
31 int[] nums = {3, 5, 6, 7};
32 int target = 9;
33 System.out.println(solution.numSubseq(nums, target));
34 }
35}In this Java solution, precomputing powers of 2 offers a tailored optimization by avoiding repeated computation of power values within the pointer loop. Pre-sorting organizes the data for easier traversal through nested pairs.