1498. Number of Subsequences That Satisfy the Given Sum Condition

Number of Subsequences That Satisfy the Given Sum Condition

Problem Description

You are given an array of integers nums and an integer target.

Return the number of non-empty subsequences  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

Approach) Brute Force : O(nlogn)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var numSubseq = function(arr, target) {
    // first sort the array so that any numbers causing sum > target with minimum most element can be eliminated by decrementing right pointer
    arr.sort((a,b) => a-b);
    
    // Initialise all the values as BigInt
    let res = BigInt(0);
    let mod = BigInt(10**9 +7);
    
    // initialise left, right pointers
    let l = 0;
    let r = arr.length-1;
    
    
    while(l <= r) {
        
        // while l+r values not less than target decrease right pointer
        while(arr[l]+arr[r] > target && r >= l)  {
            r--;
        }
        
        if(l <= r) {
            // count the possible subsets of r-l elements
            res = (res + BigInt(2)**BigInt(r-l))%mod;
        }
        l++;
    }
    return Number(res);
};

Approach) Brute Force : O(nlogn)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var numSubseq = function(nums, target) {
   nums.sort((a,b)=>{return a-b})
   let i=0,j=nums.length-1,count=0,mod = (10**9 + 7)
   
   let powers = pow(2,nums.length,mod)
   
   while(i<=j){
       if((nums[i] + nums[j]) > target){
           j -= 1
       }else{
           count = (count + powers[j-i])%mod
           i+=1
       }
   }
    
    return count%mod
};

let pow = (base,power,mod)=>{
    let powers = [1],res=1
    for(let i=1;i<=power;i++){
        res = (res*base)%mod
        powers.push(res)
    }
    return powers
}

Approach) Two Pointer

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
*/
var numSubseq = function(nums, target) {
    nums.sort((b, a) => b - a);
    
    let l = 0, r = nums.length - 1, mod = 1e9 + 7, ans = 0;

    let combinations = [1];
    
    const sumCombinations = (l, r) => {
        let i = 0, sum = 1;
        while (++i <= r - l) {
            combinations[i] = (combinations[i - 1] * 2) % mod;
        }

        return combinations[i - 1];
    };

    while (l <= r) {
        if (nums[l] + nums[r] > target) {
            r--;
        } else {
            ans =
                (ans +
                    (combinations[r - l] === undefined
                        ? sumCombinations(l, r)
                        : combinations[r - l])) %
                mod;
            l++;
        }
    }

    return ans;
};

Approach) Sort and Shrinking Window: O(nlogn)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
*/
var numSubseq = function(nums, target) {
    const mod = 1000000007;
    const powersOf2 = [];
    let powerOf2 = 1;
    for (let i = 0; i < nums.length; i++) {
        powersOf2.push(powerOf2);
        powerOf2 = powerOf2 * 2 % mod;
    }
    
    nums.sort((a,b) => a - b);
    
    let count = 0;
    let j = nums.length - 1;
    for (let i = 0; i < nums.length && nums[i] + nums[i] <= target; i++) {
        while (j && nums[j] + nums[i] > target) j--;
        count = (count + powersOf2[j - i]) % mod;
    }
    return count;
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #1498. Number of Subsequences That Satisfy the Given Sum Condition

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!