Number of Subsequences That Satisfy the Given Sum Condition
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
class Solution { private static final int MOD = 1_000_000_007; public int numSubseq(int[] nums, int target) { Arrays.sort(nums); int[] pow = new int[nums.length]; pow[0] = 1; for(int i=1;i<pow.length;i++){ pow[i] = (pow[i-1]*2)%MOD; } int right = nums.length-1; //for each left as minimum //find the right such that nums[left]+nums[right]<= target int count = 0; for(int left=0;left<nums.length;left++){ while(right > -1 && nums[left]+nums[right]>target){ right--; } //count subsequences such that left would be minimum in that subsequence if(left <= right) count = (count + pow[right-left])%MOD; } return count; } //TLE // public int numSubseq(int[] nums, int target) { // Arrays.sort(nums); // int count = dfs(nums, 100001, 0, target, 0); // return count; // } // //7, 10, 7, 3, 7, 5, 4 // //3, 4, 5, 7, 7, 7, 10 // private int dfs(int[] nums, int min, int max, int target, int i){ // if(i>=nums.length){ // return 0; // } // //either you can pick it // int currMin = Math.min(min, nums[i]); // int currMax = Math.max(max, nums[i]); // int count = 0; // //you can only pick it if currMin + currMax <= target // if(currMin + currMax <= target){ // count = 1 + dfs(nums, currMin, currMax, target, i+1); // } // //or you don't pick it // count = count + dfs(nums, min, max, target, i+1); // return count; // } } |
Time Complexity
O(nlogn), where n is the number of elements in the array
Space Complexity
O(n) to store 2’s pow