Description
Solutions
Count Subsequences
🤘 INTERN

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)

    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
    Thumbnail 0

    Testcase

    Result
    Case 1

    input:

    output: