Count Subsequences
Bank of New York Mellon● HardINTERNOAProblem statement
In the context of training a machine learning model for data pattern detection and categorization, there is a dataset represented as an array of n integers, arr[i], where 1<=i<=n. Determine the number of subsequences within this array that possess a Minimum Excludant (MEX) value falling within a specified range ([l, r]), inclusively bounded where l<=r. To optimize computational efficiency, the result should be returned modulo ((10^9 + 7)). This closely simulates data processing and modeling challenges often encountered in machine learning workflows.
Note:
- A subsequence of a given array can be defined as a sequence that results from removing elements from the array at any position without altering the relative order of the remaining elements. An empty subsequence contains no elements.
- The Minimum Excludant (MEX) of a sequence is the smallest non-negative integer that is absent from the sequence. The MEX of an empty subsequence is zero.
Function
countSubsequences(arr: List<Integer>, l: int, r: int) → int
Complete the function countSubsequences in the editor.
countSubsequences has the following parameters:
List arr: an array of integersint l: the lower bound of the rangeint r: the upper bound of the range
Returns
int: the number of subsequences with MEX within the range [l, r], modulo (10^9 + 7)
Examples
Example 1
arr = [0, 1, 2]l = 1r = 2return = 3The Minimum Excludant (MEX) for all possible subsequences is demonstrated as follows:
- An empty subsequence ([]) has a MEX of 0.
- A subsequence ([0]) has a MEX of 1.
- A subsequence ([1]) has a MEX of 0.
- A subsequence ([2]) has a MEX of 0.
- For the subsequence ([0, 1]), the MEX is 2.
- In the case of ([0, 2]), the MEX is 1.
- In the case of ([1, 2]), the MEX is 0.
- Finally, when considering the subsequence [0,1,2], the MEX is 3,
There are 2 subsequences with MEX of 1 and 1 subsequence with a MEX of 2. Hence, the answer is 1+2=3.
Constraints
1<=n<=3*10^50<=arr[i]<=10^90<=l<=r<=10^9