Depend variety of Subsequences in Array wherein X and Y are min and max components

By
Sohaib
-
0
8
Adv1


Adv2

Given an array arr[] consisting of N distinctive components, the duty is to return the depend of the subsequences in an array wherein the minimal factor is X and the utmost factor is Y.

Examples:

Enter: arr[] = {2, 4, 6, 7, 5}, X = 2, Y = 5
Output: 2
Rationalization: Subsequences wherein the minimal factor is X and the utmost factor 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 wherein the minimal factor is X and the utmost factor 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 Method: The fundamental method to resolve the issue is as follows:

The given drawback may be solved by producing and counting all doable subsequences of the given array utilizing recursion and checking if every subsequence has the minimal factor as X and the utmost factor as Y.

Beneath is the code for the above strategy:

C++

#embrace <bits/stdc++.h>

utilizing namespace std;

  

int Subsequences(vector<int>& arr, int index,

                 vector<int>& subarr, int n, int x, int y)

{

  

    if (index == n) {

  

        

        

        if (subarr.dimension() != 0 && subarr[0] == x

            && subarr[subarr.size() - 1] == y) {

  

            

            

            return 1;

        }

        else

            return 0;

    }

    else {

  

        

        

        subarr.push_back(arr[index]);

  

        

        

        

        int pic

            = Subsequences(arr, index + 1, subarr, n, x, y);

  

        

        

        subarr.pop_back();

  

        

        

        

        int notpic

            = Subsequences(arr, index + 1, subarr, n, x, y);

  

        

        

        return pic + notpic;

    }

}

  

int fundamental()

{

    vector<int> arr = { 2, 4, 6, 7, 5, 1, 9, 10, 11 };

    int x = 2, y = 7;

    vector<int> subarr;

  

    

    type(arr.start(), arr.finish());

  

    

    

    cout << Subsequences(arr, 0, subarr, arr.dimension(), x, y);

  

    return 0;

}

Time Complexity: O(2n)
Auxiliary House: O(n)

Environment friendly Method: To resolve the issue observe the beneath concept:

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

Beneath are the steps for the above strategy:

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

Beneath is the code for the above strategy:

C++

#embrace <bits/stdc++.h>

utilizing namespace std;

  

int countSubsequences(int arr[], int n, int x, int y)

{

  

    

    

    

    int cnt = 0;

    for (int i = 0; i < n; i++) {

  

        

        

        if (arr[i] > x && arr[i] < y) {

  

            

            cnt++;

        }

    }

  

    

    

    

    return (1 << cnt);

}

  

int fundamental()

{

    int arr[] = { 2, 4, 6, 7, 5 };

  

    

    int n = sizeof(arr) / sizeof(arr[0]);

    int x = 2, y = 5;

  

    

    

    cout << countSubsequences(arr, n, x, y) << endl;

    return 0;

}

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

Adv3