FastPrepFastPrep
Problem Brief

Count Good Subsequences

FULLTIMEOA

A sequence of numbers is said to be good if it satisfies the following two conditions:

  1. All elements in the sequence are unique.
  2. If the minimum element in the sequence is a, and the maximum element in the sequence is b, then all numbers in the range [a, b] are present in the sequence.

For example, (4, 2, 5, 1, 3) is a good sequence, while (2, 2, 1) or (3, 7) are not.

A subsequence of an array arr is a sequence that can be derived from the array arr by deleting some or no elements without changing the order of the remaining elements. Given an array of n integers, find the number of different good subsequences. Two subsequences are considered different if they include at least one different index. For example, for the sequence (2, 2, 1), both (2, 1) formed by indices 1 and 2 and (2, 1) formed by indices 0 and 2 are considered different subsequences.

Function Description

Complete the function countGoodSubsequences in the editor.

countGoodSubsequences has the following parameter:

  • int arr[n]: the given array of integers

    • Returns

    long integer: the number of good subsequences which can be derived from the array.

    1Example 1

    Input
    arr = [13, 11, 4, 12, 5, 4]
    Output
    11
    Explanation
    We can form the following good subsequences:
  • Subsequences of length 1: [13], [11], [4], [12], [5], [4]
  • Subsequences of length 2: [13, 12], [11, 1], [12, 4], [5, 4]
  • Subsequences of length 3: [13, 11, 12]
    • Thus, the answer is 6 + 4 + 1 = 11.

    Constraints

    Limits and guarantees your solution can rely on.

    • 1 ≤ n ≤ 10^5
    • 1 ≤ arr[i] ≤ 10^5, for all i
    public long countGoodSubsequences(int[] arr) {
  // write your code here
}
    Input

    arr

    [13, 11, 4, 12, 5, 4]

    Output

    11

    Sign in to submit your solution.