Number of Subsequences That Satisfy the Given Sum Condition

Updated on 20 June, 2025
Number of Subsequences That Satisfy the Given Sum Condition header image

Problem Statement

In this problem, you are provided with an array of integers nums and a single integer target. Your task is to find out how many non-empty subsequences of nums have the property that the sum of the minimum and maximum elements of the subsequence is less than or equal to target. A subsequence is defined as a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. Due to the potentially large size of the output, the result should be returned modulo 10^9 + 7.

Examples

Example 1

Input:

nums = [3,5,6,7], target = 9

Output:

4

Explanation:

There are 4 subsequences that satisfy the condition.  
[3] -> Min + Max = 3 + 3 = 6  
[3,5] -> 3 + 5 = 8  
[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.  
[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 total.  
Only [6,7] and [7] violate the rule.  
So valid count = 63 - 2 = 61  

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6
  • 1 <= target <= 10^6

Approach and Intuition

Intuition

The key is to determine how many subsequences satisfy: min(subsequence) + max(subsequence) <= target.

Approach

  1. Sort the Array: This ensures that for any fixed starting point (the smallest value), the valid maximums are to its right.

  2. Two-Pointer Technique: Use two pointers left and right. For each left, increment right while nums[left] + nums[right] <= target.

  3. Count Valid Subsequences: Every element between left and right (inclusive) can either be chosen or not, except left must be included. So total = 2^(right - left) valid subsequences.

  4. Use Modulo: Since the count can be large, use modulo 10^9 + 7 for all calculations.

This efficient approach ensures we don't explicitly generate subsequences and still compute the valid count within acceptable time for large inputs.

Solutions

  • Java
  • Python
java
class Solution {
    public static int binarySearchInsertPos(int[] array, int goal) {
        int start = 0, end = array.length - 1;
        while (start <= end) {
            int center = start + (end - start) / 2;
            if (array[center] <= goal) {
                start = center + 1;
            } else {
                end = center - 1;
            }
        }
        return start;
    }
        
    public int countSubsequences(int[] array, int limit) {
        int size = array.length;
        int modulo = 1_000_000_007;
        Arrays.sort(array);
            
        int[] powers = new int[size];
        powers[0] = 1;
        for (int i = 1; i < size; ++i) {
            powers[i] = (powers[i - 1] * 2) % modulo;
        }
            
        int result = 0;
    
        for (int leftIndex = 0; leftIndex < size; leftIndex++) {
            int rightIndex = binarySearchInsertPos(array, limit - array[leftIndex]) - 1;
            if (rightIndex >= leftIndex) {
                result += powers[rightIndex - leftIndex];
                result %= modulo;
            }
        }
            
        return result;
    }
}

Solve the problem of finding the number of subsequences in an array that meet a certain sum condition by applying the provided Java solution. Understand the approach of using binary search for efficiency and modular arithmetic to handle large numbers.

  • First, sort the input array to simplify the search for subsequences satisfying the sum condition.
  • Calculate power of twos up to the array's length using modular arithmetic. This is to efficiently compute the number of subsequences.
  • For each element in the array, use the helper method binarySearchInsertPos to find the appropriate position in the array where the sum condition breaches. This method returns the position to insert an element, which indirectly helps in identifying valid subsequences' upper bound.
  • Count valid subsequences from the current element's index to the calculated upper bound using powers of two. This exploits the property that for sorted arrays, every subsequence formed with the current element and elements before the upper bound is valid.
  • Handle large result numbers by taking modulo $10^9 + 7$ at each step to prevent integer overflows.

Each iteration effectively counts the number of valid subsequences involving the current element of the array, ensuring the solution is both efficient and straightforward to implement. The combination of sorting, binary search, and modular arithmetic provides a robust framework for solving similar problems in subsequence counting under specific constraints.

python
class Solution:
    def countSubsequences(self, arr: List[int], limit: int) -> int:
        length = len(arr)
        modulus = 10 ** 9 + 7
        arr.sort()
            
        result = 0
            
        for start in range(length):
            end = bisect.bisect_right(arr, limit - arr[start]) - 1
            if end >= start:
                result += pow(2, end - start, modulus)
            
        return result % modulus

The provided Python code solves the problem of finding the number of non-empty subsequences within a given array such that the sum of the smallest and largest elements in each subsequence is less than or equal to a specified limit. Here’s a breakdown of how the solution works:

  • Firstly, make sure the array is sorted. This order helps to easily identify the largest and smallest values in any subsequence.
  • Set up a variable result to keep count of the valid subsequences.
  • Iterate through each element of the array treating each element as the potential smallest in a subsequence.
  • For each starting element, find the end boundary (the largest number) for a valid subsequence using binary search (bisect_right). This optimizes the search by narrowing down the possible largest values under the condition that their sum with the smallest element is within the limit.
  • Calculate the number of valid subsequences from the current start to end boundary using the formula 2^(end - start), which leverages the properties of sets where each element can either be included or excluded.
  • Use modulo arithmetic to handle large numbers and prevent overflow, ensuring the result fits within typical integer limits of computational environments.
  • Return the final count of subsequences modulo 10^9 + 7, which often appears in computational problems to maintain result size manageable.

Make sure to include the standard library function bisect.bisect_right to perform the binary search over the array, optimizing the evaluation of possible subsequences. The solution is efficient, utilizing sorting alongside binary search, ensuring that the operations remain manageable even for larger sizes of input arrays.

Comments

No comments yet.