Welcome to Subscribe On Youtube
1498. Number of Subsequences That Satisfy the Given Sum Condition
Description
You are 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 to target
. Since the answer may be too large, return it modulo 109 + 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 do not satisfy the condition ([6,7], [7]). Number of valid subsequences (63 - 2 = 61).
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 106
1 <= target <= 106
Solutions
-
class Solution { public int numSubseq(int[] nums, int target) { Arrays.sort(nums); final int mod = (int) 1e9 + 7; int n = nums.length; int[] f = new int[n + 1]; f[0] = 1; for (int i = 1; i <= n; ++i) { f[i] = (f[i - 1] * 2) % mod; } int ans = 0; for (int i = 0; i < n; ++i) { if (nums[i] * 2L > target) { break; } int j = search(nums, target - nums[i], i + 1) - 1; ans = (ans + f[j - i]) % mod; } return ans; } private int search(int[] nums, int x, int left) { int right = nums.length; while (left < right) { int mid = (left + right) >> 1; if (nums[mid] > x) { right = mid; } else { left = mid + 1; } } return left; } }
-
class Solution { public: int numSubseq(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); const int mod = 1e9 + 7; int n = nums.size(); int f[n + 1]; f[0] = 1; for (int i = 1; i <= n; ++i) { f[i] = (f[i - 1] * 2) % mod; } int ans = 0; for (int i = 0; i < n; ++i) { if (nums[i] * 2L > target) { break; } int j = upper_bound(nums.begin() + i + 1, nums.end(), target - nums[i]) - nums.begin() - 1; ans = (ans + f[j - i]) % mod; } return ans; } };
-
class Solution: def numSubseq(self, nums: List[int], target: int) -> int: mod = 10**9 + 7 nums.sort() n = len(nums) f = [1] + [0] * n for i in range(1, n + 1): f[i] = f[i - 1] * 2 % mod ans = 0 for i, x in enumerate(nums): if x * 2 > target: break j = bisect_right(nums, target - x, i + 1) - 1 ans = (ans + f[j - i]) % mod return ans
-
func numSubseq(nums []int, target int) (ans int) { sort.Ints(nums) n := len(nums) f := make([]int, n+1) f[0] = 1 const mod int = 1e9 + 7 for i := 1; i <= n; i++ { f[i] = f[i-1] * 2 % mod } for i, x := range nums { if x*2 > target { break } j := sort.SearchInts(nums[i+1:], target-x+1) + i ans = (ans + f[j-i]) % mod } return }
-
function numSubseq(nums: number[], target: number): number { nums.sort((a, b) => a - b); const mod = 1e9 + 7; const n = nums.length; const f: number[] = Array(n + 1).fill(1); for (let i = 1; i <= n; ++i) { f[i] = (f[i - 1] * 2) % mod; } let ans = 0; for (let i = 0; i < n && nums[i] * 2 <= target; ++i) { const j = search(nums, target - nums[i], i + 1) - 1; if (j >= i) { ans = (ans + f[j - i]) % mod; } } return ans; } function search(nums: number[], x: number, left: number): number { let right = nums.length; while (left < right) { const mid = (left + right) >> 1; if (nums[mid] > x) { right = mid; } else { left = mid + 1; } } return left; }
-
impl Solution { pub fn num_subseq(mut nums: Vec<i32>, target: i32) -> i32 { nums.sort(); const MOD: i32 = 1_000_000_007; let n = nums.len(); let mut f = vec![1; n + 1]; for i in 1..=n { f[i] = (f[i - 1] * 2) % MOD; } let mut ans = 0; for i in 0..n { if nums[i] * 2 > target { break; } let mut l = i + 1; let mut r = n; while l < r { let m = (l + r) / 2; if nums[m] > target - nums[i] { r = m; } else { l = m + 1; } } let j = l - 1; ans = (ans + f[j - i]) % MOD; } ans } }