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:
Function Description
Complete the function countSubsequences
in the editor.
countSubsequences
has the following parameters:
List
: an array of integersarr int 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)
Example 1:
Input: arr = [0, 1, 2], l = 1, r = 2
Output: 3
Explanation:The 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.
1<=n<=3*10^5
0<=arr[i]<=10^9
0<=l<=r<=10^9

input:
output: