We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Subsequences That Satisfy the Given Sum Condition

Number: 1621

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Bloomberg, Google, Adobe, Turing

Problem Description

Given an array of integers nums and an integer target, count the number of non-empty subsequences such that the sum of the minimum and maximum elements in each subsequence is less than or equal to target. Since the result can be very large, return the answer modulo 10^9 + 7.

Key Insights

  • Sort the array to efficiently identify valid minimum and maximum pairs.
  • Use the two-pointers technique with one pointer at the beginning and one at the end.
  • When a valid pair (nums[left] + nums[right] <= target) is found, every combination of the elements between these pointers forms a valid subsequence.
  • Precompute powers of 2 to quickly compute the number of valid combinations.
  • Use modulo operations to manage large numbers.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting, plus O(n) for the two-pointer scan. Space Complexity: O(n) for the precomputed powers array.

Solution

Start by sorting the nums array. Then, initialize two pointers: left at the beginning and right at the end. For every valid pair where nums[left] + nums[right] <= target, calculate the number of subsequences that can be formed using the elements between left and right, which is 2^(right - left) (using precomputed powers of 2 to speed up the process). Add this number to the result and move the left pointer; if the pair is not valid, move the right pointer instead. Continue until the pointers cross.

Code Solutions

MOD = 10**9 + 7

def numSubseq(nums, target):
    # Sort the array for two pointers approach
    nums.sort()
    n = len(nums)
    
    # Precompute powers of 2 modulo MOD up to n elements.
    power_of_two = [1] * n
    for i in range(1, n):
        power_of_two[i] = (power_of_two[i - 1] * 2) % MOD
    
    left, right = 0, n - 1
    result = 0
    
    # Use two pointers to check each potential pair of numbers
    while left <= right:
        # If the current pair satisfies the sum condition
        if nums[left] + nums[right] <= target:
            # All subsequences formed by choices between left and right are valid.
            result = (result + power_of_two[right - left]) % MOD
            left += 1
        else:
            # If condition not satisfied, reduce the maximum candidate.
            right -= 1
            
    return result

# Example usage:
print(numSubseq([3,5,6,7], 9))    # Output: 4
print(numSubseq([3,3,6,8], 10))   # Output: 6
print(numSubseq([2,3,3,4,6,7], 12))  # Output: 61
← Back to All Questions