Rely variety of Subsequences in Array by which X and Y are min and max parts

Given an array arr[] consisting of N distinctive parts, the duty is to return the depend of the subsequences in an array by which the minimal component is X and the utmost component is Y.

Examples:

Enter: arr[] = {2, 4, 6, 7, 5}, X = 2, Y = 5
Output: 2
Rationalization: Subsequences by which the minimal component is X and the utmost component is Y are {2, 5}, {2, 4, 5}.

Enter: arr[] = {2, 4, 6, 7, 5, 1, 9, 10, 11}, X = 2, Y = 7
Output: 8
Rationalization: subsequences by which the minimal component is X and the utmost component is Y are {2, 4, 6, 7, 5}, {2, 4, 7, 5}, {2, 4, 6, 7}, {2, 4, 7}, {2, 6, 7, 5}, {2, 7, 5}, {2, 6, 7}, {2, 7}

Naive Strategy: The fundamental method to remedy the issue is as follows:

The given downside could be solved by producing and counting all attainable subsequences of the given array utilizing recursion and checking if every subsequence has the minimal component as X and the utmost component as Y.

Beneath is the code for the above method:

Time Complexity: O(2ⁿ)
Auxiliary Area: O(n)

Environment friendly Strategy: To resolve the issue comply with the beneath concept:

We all know that the subsequence can be shaped can be within the vary (X, Y), and the system that can come for all of the subsequence within the vary (X, Y) excluding X and Y can be 2ⁿ the place n is the variety of parts within the vary X and Y. Subsequently will return the twoⁿ as the reply.

Beneath are the steps for the above method:

• Initialize a counter variable say, cnt = 0 to maintain monitor of the variety of parts within the vary [X, Y].
• Run a loop from i = 0 to i < n and verify if the component lies throughout the vary (x, y),
  • if (arr[i] > X && arr[i] < Y), increment the cnt variable by 1.
• Return 2^cnt, which supplies us the variety of subsequences, and return 1 << cnt.

Beneath is the code for the above method:

Time Complexity: O(n)
Auxiliary Area: O(1)