1498. Number of Subsequences That Satisfy the Given Sum Condition #1866
-
Topics: You are given an array of integers Return the number of non-empty subsequences of Example 1:
Example 2:
Example 3:
Constraints:
Hint:
|
Beta Was this translation helpful? Give feedback.
Replies: 1 comment 2 replies
-
We need to count the number of non-empty subsequences in an array where the sum of the minimum and maximum elements in each subsequence is less than or equal to a given target. Given the constraints, a brute-force approach is infeasible, so we use sorting and a two-pointer technique to efficiently count valid subsequences. Approach
Let's implement this solution in PHP: 1498. Number of Subsequences That Satisfy the Given Sum Condition <?php
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer
*/
function numSubseq($nums, $target) {
$mod = 1000000007;
sort($nums);
$n = count($nums);
$pow2 = array_fill(0, $n, 1);
for ($i = 1; $i < $n; $i++) {
$pow2[$i] = ($pow2[$i-1] * 2) % $mod;
}
$j = $n - 1;
$ans = 0;
for ($i = 0; $i < $n; $i++) {
while ($j >= $i && $nums[$i] + $nums[$j] > $target) {
$j--;
}
if ($j < $i) {
break;
}
$ans = ($ans + $pow2[$j - $i]) % $mod;
}
return $ans;
}
// Test cases
$nums1 = [3, 5, 6, 7];
$target1 = 9;
echo numSubseq($nums1, $target1) . "\n"; // Output: 4
$nums2 = [3, 3, 6, 8];
$target2 = 10;
echo numSubseq($nums2, $target2) . "\n"; // Output: 6
$nums3 = [2, 3, 3, 4, 6, 7];
$target3 = 12;
echo numSubseq($nums3, $target3) . "\n"; // Output: 61
?> Explanation:
This approach efficiently counts all valid subsequences by leveraging sorting, precomputation, and a two-pointer technique, ensuring optimal performance for large input sizes. |
Beta Was this translation helpful? Give feedback.
We need to count the number of non-empty subsequences in an array where the sum of the minimum and maximum elements in each subsequence is less than or equal to a given target. Given the constraints, a brute-force approach is infeasible, so we use sorting and a two-pointer technique to efficiently count valid subsequences.
Approach