Leetcode 1498: Number of Subsequences That Satisfy the Given Sum Condition
You are given an array of integers nums and an integer target. Your task is to count how many non-empty subsequences of nums exist such that the sum of the minimum and maximum element in each subsequence is less than or equal to target. Return the result modulo 10^9 + 7.
Problem
Approach
Steps
Complexity
Input: The input consists of an integer array nums and an integer target.
Example: nums = [2, 5, 7, 8], target = 10
Constraints:
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6
• 1 <= target <= 10^6
Output: Return the number of valid subsequences modulo 10^9 + 7.
Example: Output: 3
Constraints:
• The result should be returned modulo 10^9 + 7.
Goal: The goal is to count subsequences where the sum of the minimum and maximum elements in the subsequence is less than or equal to the given target.
Steps:
• Sort the array to efficiently find pairs of subsequences where the sum of the minimum and maximum values is <= target.
• Use a sliding window technique to count valid subsequences.
• For each element, calculate the number of subsequences that can be formed with that element as the minimum, using binary search to find the maximum valid subsequence.
Goal: The input array has a length between 1 and 10^5, and each element of the array is between 1 and 10^6.
Steps:
• The length of the input array nums is between 1 and 10^5.
• Each element in nums is between 1 and 10^6.
• The target value is between 1 and 10^6.
Assumptions:
• The input array always has at least one element.
• Input: nums = [2, 5, 7, 8], target = 10
• Explanation: The valid subsequences are: [2], [2, 5], [2, 5, 7], and [2, 7]. All of their minimum and maximum sums are less than or equal to 10.
• Input: nums = [1, 3, 5, 7], target = 8
• Explanation: The valid subsequences are: [1], [3], [1, 3], and [1, 5], which satisfy the condition.
Approach: We can solve this problem using a sorted array and a sliding window technique to count valid subsequences. The number of subsequences can be computed using the binary search technique to find the range of valid subsequences.
Observations:
• Sorting the array helps find subsequences with valid sums of minimum and maximum elements.
• The key observation is that once the array is sorted, finding the valid subsequences becomes a matter of using two pointers or binary search.
Steps:
• Sort the input array.
• For each element in the array, calculate how many subsequences can be formed with that element as the minimum, where the maximum element is within the target sum constraint.
• Use binary search to quickly find the valid subsequences for each element.
Empty Inputs:
• The input array will never be empty, as it is guaranteed to have at least one element.
Large Inputs:
• The solution should efficiently handle arrays of size up to 10^5.
Special Values:
• If all elements in nums are the same, the valid subsequences are just the combinations of that element.
Constraints:
• The solution must work within the given time limits for large inputs.
int mod = (int) 1e9 + 7;
int pow2(int idx) {
if(idx == 0) return 1;
long res;
if(idx % 2) {
res = pow2(idx / 2);
res = (res * res * 2) % mod;
}else {
res = pow2(idx / 2);
res = (res * res) % mod;
}
return res;
}
int numSubseq(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
long res = 0, n = nums.size();
for(int i = 0; i < n; i++) {
if(nums[i] * 2 > target) break;
int end = target - nums[i];
auto it = upper_bound(nums.begin(), nums.end(), end);
int idx = it - nums.begin();
res = (res + pow2(idx - i - 1)) % mod;
}
return res;
}
1 : Modulo Initialization
int mod = (int) 1e9 + 7;
Set the value of `mod` to (10^9 + 7), a large prime used for modulo operations to prevent integer overflow in the result calculations.
2 : Power Function Declaration
int pow2(int idx) {
Define the `pow2` function which calculates (2^{idx} % ext{mod}). It uses recursion and the properties of exponents for efficient computation.
3 : Base Case
if(idx == 0) return 1;
If the exponent is 0, return 1, as any number raised to the power of 0 is 1.
4 : Variable Declaration
long res;
Declare a variable `res` to store the result of the power calculation.
5 : Odd Exponent Check
if(idx % 2) {
If the exponent is odd, proceed to calculate (2^{idx} % ext{mod}) by splitting it into smaller subproblems.
6 : Recursive Call for Odd Exponent
res = pow2(idx / 2);
Recursively calculate (2^{ rac{idx}{2}} % ext{mod}).
7 : Odd Exponent Final Calculation
res = (res * res * 2) % mod;
For an odd exponent, square the result of the recursive call and multiply by 2 to get (2^{idx} % ext{mod}).
8 : Even Exponent Calculation
}else {
If the exponent is even, calculate the power using the even exponent property.
9 : Recursive Call for Even Exponent
res = pow2(idx / 2);
Recursively calculate (2^{ rac{idx}{2}} % ext{mod}).
10 : Even Exponent Final Calculation
res = (res * res) % mod;
For an even exponent, square the result of the recursive call to get (2^{idx} % ext{mod}).
11 : Return Final Result
return res;
Return the calculated result of (2^{idx} % ext{mod}).
12 : Main Function Declaration
int numSubseq(vector<int>& nums, int target) {
Declare the `numSubseq` function, which calculates the number of subsequences in the array `nums` whose sum of the smallest and largest element is less than or equal to `target`.
13 : Sorting
sort(nums.begin(), nums.end());
Sort the array `nums` in non-decreasing order to facilitate the calculation of valid subsequences.
14 : Variable Initialization
long res = 0, n = nums.size();
Initialize a result variable `res` to 0 and a variable `n` to store the size of the array `nums`.
15 : Loop Over Array
for(int i = 0; i < n; i++) {
Loop through the elements of the sorted array `nums`.
16 : Target Check
if(nums[i] * 2 > target) break;
If the current element is greater than half of `target`, no valid subsequences can be formed, so exit the loop.
17 : Calculate Upper Bound
int end = target - nums[i];
Calculate the maximum possible value for the largest element of the subsequence, `end`, by subtracting `nums[i]` from `target`.
18 : Binary Search
auto it = upper_bound(nums.begin(), nums.end(), end);
Use binary search to find the first element in `nums` that is greater than `end`.
19 : Calculate Index
int idx = it - nums.begin();
Calculate the index of the element found by `upper_bound` to determine how many valid subsequences can be formed.
20 : Add to Result
res = (res + pow2(idx - i - 1)) % mod;
Add the number of valid subsequences formed between `i` and `idx - 1` to the result, using the `pow2` function to calculate powers of 2.
21 : Return Final Result
return res;
Return the final result, the total number of valid subsequences.
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)
Description: The time complexity is O(n log n) because the array is sorted and binary search is performed for each element.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the space used for sorting the array and storing intermediate results.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus