FastPrep

Description

Solutions

Count Subsequences

🤘 INTERN📚RELATED PROBLEMS

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 Description

Complete the function countSubsequences in the editor.

countSubsequences has the following parameters:

List arr: an array of integers
int l: the lower bound of the range
int 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.

Constraints:

1<=n<=3*10^5
0<=arr[i]<=10^9
0<=l<=r<=10^9