
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
Sort the Array: This ensures that for any fixed starting point (the smallest value), the valid maximums are to its right.
Two-Pointer Technique: Use two pointers
left
andright
. For eachleft
, incrementright
whilenums[left] + nums[right] <= target
.Count Valid Subsequences: Every element between
left
andright
(inclusive) can either be chosen or not, exceptleft
must be included. So total =2^(right - left)
valid subsequences.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
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.
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
toend
boundary using the formula2^(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.
No comments yet.