FastPrepFastPrep
Problem Brief

Count Subsequences

INTERNOA

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:

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

    1Example 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

    Limits and guarantees your solution can rely on.

    • 1<=n<=3*10^5
    • 0<=arr[i]<=10^9
    • 0<=l<=r<=10^9
    public int countSubsequences(List<Integer> arr, int l, int r) {
  // write your code here
}
    Input

    arr

    [0, 1, 2]

    l

    1

    r

    2

    Output

    3

    Sign in to submit your solution.