Count number of Subsequences in Array in which X and Y are min and max elements
Given an array arr[] consisting of N unique elements, the task is to return the count of the subsequences in an array in which the minimum element is X and the maximum element is Y.
Examples:
Input: arr[] = {2, 4, 6, 7, 5}, X = 2, Y = 5
Output: 2
Explanation: Subsequences in which the minimum element is X and the maximum element is Y are {2, 5}, {2, 4, 5}.Input: arr[] = {2, 4, 6, 7, 5, 1, 9, 10, 11}, X = 2, Y = 7
Output: 8
Explanation: subsequences in which the minimum element is X and the maximum element 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 Approach: The basic way to solve the problem is as follows:
The given problem can be solved by generating and counting all possible subsequences of the given array using recursion and checking if each subsequence has the minimum element as X and the maximum element as Y.
Below is the code for the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; int Subsequences(vector< int >& arr, int index, vector< int >& subarr, int n, int x, int y) { if (index == n) { // If the subsequence is valid // return 1; if (subarr.size() != 0 && subarr[0] == x && subarr[subarr.size() - 1] == y) { // Increment count of valid // subsequences return 1; } else return 0; } else { // Pick the current index into // the subsequence. subarr.push_back(arr[index]); // Recursive call to consider the // remaining elements in // the subsequence int pic = Subsequences(arr, index + 1, subarr, n, x, y); // Backtrack to remove the current // index from the subsequence subarr.pop_back(); // Recursive call to not consider // the current element in // the subsequence int notpic = Subsequences(arr, index + 1, subarr, n, x, y); // Sum the counts of valid // subsequences return pic + notpic; } } // Drivers code int main() { vector< int > arr = { 2, 4, 6, 7, 5, 1, 9, 10, 11 }; int x = 2, y = 7; vector< int > subarr; // Sort the array to simplify the search sort(arr.begin(), arr.end()); // Call the recursive function to find // all valid subsequences cout << Subsequences(arr, 0, subarr, arr.size(), x, y); return 0; } |
Java
// / Java code for the above approach: import java.util.*; public class Main { public static int Subsequences(ArrayList<Integer> arr, int index, ArrayList<Integer> subarr, int n, int x, int y) { // If the subsequence is valid // return 1; if (index == n) { if (subarr.size() != 0 && subarr.get( 0 ) == x && subarr.get(subarr.size() - 1 ) == y) { // Increment count of valid // subsequences return 1 ; } else { return 0 ; } } else { // Pick the current index into // the subsequence. subarr.add(arr.get(index)); // Recursive call to consider the // remaining elements in // the subsequence int pic = Subsequences(arr, index + 1 , subarr, n, x, y); // Backtrack to remove the current // index from the subsequence subarr.remove(subarr.size() - 1 ); // Recursive call to not consider // the current element in // the subsequence int notpic = Subsequences(arr, index + 1 , subarr, n, x, y); // Sum the counts of valid // subsequences return pic + notpic; } } // Drivers code public static void main(String[] args) { ArrayList<Integer> arr = new ArrayList<Integer>( Arrays.asList( 2 , 4 , 6 , 7 , 5 , 1 , 9 , 10 , 11 )); int x = 2 , y = 7 ; ArrayList<Integer> subarr = new ArrayList<Integer>(); // Sort the array to simplify the search Collections.sort(arr); // Call the recursive function to find // all valid subsequences System.out.println( Subsequences(arr, 0 , subarr, arr.size(), x, y)); } } |
Python3
# Python3 code for the above approach: def Subsequences(arr, index, subarr, n, x, y): if index = = n: # If the subsequence is valid, return 1 if subarr and subarr[ 0 ] = = x and subarr[ - 1 ] = = y: # Increment count of valid subsequences return 1 else : return 0 else : # Pick the current index into the subsequence subarr.append(arr[index]) # Recursive call to consider the remaining elements in the subsequence pic = Subsequences(arr, index + 1 , subarr, n, x, y) # Backtrack to remove the current index from the subsequence subarr.pop() # Recursive call to not consider the current element in the subsequence notpic = Subsequences(arr, index + 1 , subarr, n, x, y) # Sum the counts of valid subsequences return pic + notpic # Driver code if __name__ = = "__main__" : arr = [ 2 , 4 , 6 , 7 , 5 , 1 , 9 , 10 , 11 ] x, y = 2 , 7 subarr = [] # Sort the array to simplify the search arr.sort() # Call the recursive function to find all valid subsequences print (Subsequences(arr, 0 , subarr, len (arr), x, y)) |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { static int Subsequences(List< int > arr, int index, List< int > subarr, int n, int x, int y) { if (index == n) { // If the subsequence is valid // return 1; if (subarr.Count != 0 && subarr[0] == x && subarr[subarr.Count - 1] == y) { // Increment count of valid // subsequences return 1; } else return 0; } else { // Pick the current index into // the subsequence. subarr.Add(arr[index]); // Recursive call to consider the // remaining elements in // the subsequence int pic = Subsequences(arr, index + 1, subarr, n, x, y); // Backtrack to remove the current // index from the subsequence subarr.RemoveAt(subarr.Count - 1); // Recursive call to not consider // the current element in // the subsequence int notpic = Subsequences(arr, index + 1, subarr, n, x, y); // Sum the counts of valid // subsequences return pic + notpic; } } static void Main( string [] args) { List< int > arr = new List< int >() { 2, 4, 6, 7, 5, 1, 9, 10, 11 }; int x = 2; int y = 7; List< int > subarr = new List< int >(); // Sort the array to simplify the search arr.Sort(); // Call the recursive function to find // all valid subsequences Console.WriteLine(Subsequences(arr, 0, subarr, arr.Count(), x, y)); } } |
Javascript
// javascript code for the above approach: function Subsequences(arr, index, subarr, n, x, y) { if (index == n) { // If the subsequence is valid, return 1 if (subarr.length != 0 && subarr[0] == x && subarr[subarr.length - 1] == y) { // Increment count of valid subsequences return 1; } else { return 0; } } else { // Pick the current index into the subsequence. subarr.push(arr[index]); // Recursive call to consider the remaining elements in the subsequence. let pic = Subsequences(arr, index + 1, subarr, n, x, y); // Backtrack to remove the current index from the subsequence. subarr.pop(); // Recursive call to not consider the current element in the subsequence. let notpic = Subsequences(arr, index + 1, subarr, n, x, y); // Sum the counts of valid subsequences. return pic + notpic; } } // Drivers code let arr = [2, 4, 6, 7, 5, 1, 9, 10, 11]; let x = 2, y = 7; let subarr = []; // Sort the array to simplify the search. arr.sort(); // Call the recursive function to find all valid subsequences. console.log(Subsequences(arr, 0, subarr, arr.length, x, y)); |
8
Time Complexity: O(2n)
Auxiliary Space: O(n)
Efficient Approach: To solve the problem follow the below idea:
We know that the subsequence will be formed will be in the range (X, Y), and the formula that will come for all the subsequence in the range (X, Y) excluding X and Y will be 2n where n is the number of elements in the range X and Y. Therefore will return the 2n as the answer.
Below are the steps for the above approach:
- Initialize a counter variable say, cnt = 0 to keep track of the number of elements in the range [X, Y].
- Run a loop from i = 0 to i < n and check if the element lies within the range (x, y),
- if (arr[i] > X && arr[i] < Y), increment the cnt variable by 1.
- Return 2cnt, which gives us the number of subsequences, and return 1 << cnt.
Below is the code for the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; int countSubsequences( int arr[], int n, int x, int y) { // Initialize a counter to keep track // of the number of elements in // the range [x, y] int cnt = 0; for ( int i = 0; i < n; i++) { // Check if the element lies // within the range (x, y) if (arr[i] > x && arr[i] < y) { // If so, increment the counter cnt++; } } // Return 2 raised to the power of cnt, // which gives us the number // of subsequences return (1 << cnt); } // Drivers code int main() { int arr[] = { 2, 4, 6, 7, 5 }; // Calculate the length of the array int n = sizeof (arr) / sizeof (arr[0]); int x = 2, y = 5; // Call the countSubsequences function // and print the result cout << countSubsequences(arr, n, x, y) << endl; return 0; } |
Java
import java.util.*; public class Main { public static int countSubsequences( int [] arr, int n, int x, int y) { // Initialize a counter to keep track // of the number of elements in // the range [x, y] int cnt = 0 ; for ( int i = 0 ; i < n; i++) { // Check if the element lies // within the range (x, y) if (arr[i] > x && arr[i] < y) { // If so, increment the counter cnt++; } } // Return 2 raised to the power of cnt, // which gives us the number // of subsequences return ( 1 << cnt); } // Driver code public static void main(String[] args) { int [] arr = { 2 , 4 , 6 , 7 , 5 }; // Calculate the length of the array int n = arr.length; int x = 2 , y = 5 ; // Call the countSubsequences function // and print the result System.out.println(countSubsequences(arr, n, x, y)); } } |
Python
def countSubsequences(arr, n, x, y): # Initialize a counter to keep track # of the number of elements in # the range [x, y] cnt = 0 for i in range (n): # Check if the element lies # within the range (x, y) if arr[i] > x and arr[i] < y: # If so, increment the counter cnt + = 1 # Return 2 raised to the power of cnt, # which gives us the number # of subsequences return 1 << cnt # Drivers code arr = [ 2 , 4 , 6 , 7 , 5 ] # Calculate the length of the array n = len (arr) x, y = 2 , 5 # Call the countSubsequences function # and print the result print (countSubsequences(arr, n, x, y)) |
C#
// C# program to implement the above approach using System; public class GFG { public static int countSubsequences( int [] arr, int n, int x, int y) { // Initialize a counter to keep track // of the number of elements in // the range [x, y] int cnt = 0; for ( int i = 0; i < n; i++) { // Check if the element lies // within the range (x, y) if (arr[i] > x && arr[i] < y) { // If so, increment the counter cnt++; } } // Return 2 raised to the power of cnt, // which gives us the number // of subsequences return (1 << cnt); } // Driver code public static void Main() { int [] arr = {2, 4, 6, 7, 5}; // Calculate the length of the array int n = arr.Length; int x = 2, y = 5; // Call the countSubsequences function // and print the result Console.WriteLine(countSubsequences(arr, n, x, y)); } } // This code is contributed by Vaibhav Nandan |
Javascript
function countSubsequences(arr, x, y) { // Initialize a counter to keep track // of the number of elements in // the range [x, y] let cnt = 0; for (let i = 0; i < arr.length; i++) { // Check if the element lies // within the range (x, y) if (arr[i] > x && arr[i] < y) { // If so, increment the counter cnt++; } } // Return 2 raised to the power of cnt, // which gives us the number // of subsequences return Math.pow(2, cnt); } // Drivers code const arr = [2, 4, 6, 7, 5]; const x = 2, y = 5; console.log(countSubsequences(arr, x, y)); |
2
Time Complexity: O(n)
Auxiliary Space: O(1)