Arrays - 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 10⁹ + 7.

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)

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]

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 <= 10⁵
1 <= nums[i] <= 10⁶
1 <= target <= 10⁶

Solution 1 - Sort input array, and search for pairs of left and right numbers that satisfy <= target condition

In this approach, we are going to sort the input array first, then find matching pairs of numbers on left and right ends of array using two pointers and calculate number of subsequences that can be formed using the numbers between those pair of numbers.

Though we are sorting the original input array, it will not change number of subsequences that can be formed with the condition that sum of left and right values will be less than or equal to a target nunber.

Consider an example with nums = [3,6,7,5] and target = 9

Say we don't sort the array, then the sub sequences with target <= 9 will be [3], [3,6], [3,6,5], [3,5].
Say we sort the array, then the array becomes [3, 5, 6, 7]sub sequences with target <= 9 will be [3], [3,5], [3,5,6], [3,6].

As you can see in both cases, number of subsequences are 4.

Implementation steps:

As a first step, sort the input array.
Then, declare following variables:
- result: to hold the result and return, initialize this with 0.
- modulo: value that we will be using to divide with as mentioned in the problem statement, initialize this with 10⁹ +7.
- left: left pointer for the array, intiialize this with 0.
- right: right pointer for the array, initialize this with nums.length - 1.
Next, loop through the input array while two pointers left and right don't intersect with each other and check:
- If nums[left] + nums[right] <= target, then count the number of subsequences that can be formed using the numbers from left element to right pointer and increment left pointer. There will be 2^{(right- left)} number of subsequences with left element being present in all sunsubsequences.
  For example, consider if the subsequence is [2, 3, 4], and sub sequences with the 2 being the first element are [2], [2,3], [2,3,4] and [2,4], so we can take it as 2², since the array is 0-indexed, we can simply take 2^{right- left} = 2^2-0 = 4. After computing number of subsequences, apply modulo on the result to avoid overflow as per problem statement and store it in result.
- Otherwise, decrement right pointer.
Finally return the result.

In below implementation, we will use a custom pow(int exponent, int modulo) function and apply the modulo while calculating the 2ⁿ value, as out of the box Math.pow() doesn't work for extrenely large numbers, and we need to apply modulo. If you want to use Math.pow(), you need to run it on smaller number multiples, say 2³⁰ something like this, and then apply modulo on that, repeat this for all multiples of 30's for n.

import java.util.Arrays; public class NumberOfSubsequencesThatSatisfyTargetSumCondition { static int numSubseq(int[] nums, int target) { Arrays.sort(nums); // O ( n log n) double result = 0; int modulo = (int)Math.pow(10, 9) + 7; int left = 0; int right = nums.length -1; while(left<=right){ if(nums[left] + nums[right] <= target) { result = (result + pow( right-left, modulo)) %modulo; left++; } else{ right--; } } return (int)result; } static int pow(int exponent, int mod) { long result =1; long base = 2 %mod; while (exponent > 0) { if(exponent %2 == 1) { result = (result * base) %mod; } base = (base *base) % mod; exponent /=2; } return (int)result; } public static void main(String[] args) { System.out.println(numSubseq(new int[]{9,25,9,28,24,12,17,8,28,7,21,25,10,2,16,19,12,13,15,28,14,12,24,9,6,7,2,15,19,13,30,30,23,19,11,3,17,2,14,20,22,30,12,1,11,2,2,20,20,27,15,9,10,4,12,30,13,5,2,11,29,5,3,13,22,5,16,19,7,19,11,16,11,25,29,21,29,3,2,9,20,15,9}, 32)); System.out.println(numSubseq(new int[]{14,4,6,6,20,8,5,6,8,12,6,10,14,9,17,16,9,7,14,11,14,15,13,11,10,18,13,17,17,14,17,7,9,5,10,13,8,5,18,20,7,5,5,15,19,14}, 22)); System.out.println(numSubseq(new int[]{5,2,4,1,7,6,8}, 16)); System.out.println(numSubseq(new int[]{7,10,7,3,7,5,4}, 12)); System.out.println(numSubseq(new int[]{3,5,6,7}, 9)); System.out.println(numSubseq(new int[]{3,3,6,8}, 10)); System.out.println(numSubseq(new int[]{2,3,3,4,6,7}, 12)); } }

Complexity Analysis:

Time complexity: Above code runs in O(n log n) time where n is the length of nums array.
Space complexity: O(1), assuming that sorting will be done using in-place sorting algorithms like QuickSort.

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: