Number of Subsequences That Satisfy the Given Sum Condition

Number of Subsequences That Satisfy the Given Sum Condition

What is this problem about?

The Number of Subsequences That Satisfy the Given Sum Condition problem asks you to count non-empty subsequences of an array where min(subsequence) + max(subsequence) ≤ target. Since subsequences can pick any elements, sorting doesn't change which valid subsequences exist (only which element is min/max). This coding problem uses a two-pointer approach after sorting.

Why is this asked in interviews?

Microsoft, Meta, Amazon, Google, and Bloomberg ask this because the key insight — sorting preserves validity while allowing two-pointer pairing of min and max — is non-obvious. Once sorted, fixing the minimum (left pointer) and finding the rightmost valid maximum (right pointer) lets you count all valid subsequences between them in O(1) using powers of 2. The array, sorting, two pointers, and binary search interview pattern is the core.

Algorithmic pattern used

Sort + two pointers + precomputed powers of 2. Sort the array. Two pointers: left = 0, right = n-1. While left ≤ right: if arr[left] + arr[right] ≤ target, all 2^(right-left) subsequences with arr[left] as minimum are valid (any subset of elements between them). Add to count. Advance left. Otherwise, decrement right. Precompute pow2 mod 10^9+7.

Example explanation

arr=[3,5,6,7], target=9. Sort: [3,5,6,7].

• left=0(3), right=3(7): 3+7=10 > 9. right=2.
• left=0(3), right=2(6): 3+6=9 ≤ 9. 2^(2-0)=4 subsequences. Count=4. left=1.
• left=1(5), right=2(6): 5+6=11 > 9. right=1.
• left=1(5), right=1(5): 5+5=10 > 9. right=0. left > right, stop. Answer = 4 (mod 10^9+7).

Common mistakes candidates make

• Not precomputing powers of 2 (recomputing with pow(2, k, mod) per iteration is slow).
• Off-by-one in the exponent: right - left elements can be chosen freely (not right-left+1).
• Forgetting to apply modulo when adding to count.
• Using binary search instead of two pointers (works but less elegant).

Interview preparation tip

Two-pointer problems where sorting doesn't invalidate the solution are a common interview pattern. After sorting, fix one pointer (min) and find the farthest valid partner (max) using the other pointer. The count of subsequences between them is a power of 2. Precompute all needed powers of 2 up to n before the two-pointer loop. Practice "count subsequences with min+max ≤ target" variants with different constraints to build this intuition.