Count of possible subarrays and subsequences using given length of Array
Given an integer N which denotes the length of an array, the task is to count the number of subarray and subsequence possible with the given length of the array.
Examples:
Input: N = 5
Output:
Count of subarray = 15
Count of subsequence = 32
Input: N = 3
Output:
Count of subarray = 6
Count of subsequence = 8
Approach: The key observation fact for the count of the subarray is the number of ends position possible for each index elements of the array can be (N – i), Therefore the count of the subarray for an array of size N can be:
Count of Sub-arrays = (N) * (N + 1) --------------- 2
The key observation fact for the count of the subsequence possible is each element of the array can be included in a subsequence or not. Therefore, the choice for each element is 2.
Count of subsequences = 2N
Below is the implementation of the above approach:
C++
// C++ implementation to count // the subarray and subsequence of // given length of the array #include <bits/stdc++.h> using namespace std; // Function to count the subarray // for the given array int countSubarray( int n){ return ((n)*(n + 1))/2; } // Function to count the subsequence // for the given array length int countSubsequence( int n){ return pow (2, n); } // Driver Code int main() { int n = 5; cout << (countSubarray(n)) << endl; cout << (countSubsequence(n)) << endl; return 0; } // This code is contributed by mohit kumar 29 |
Java
// Java implementation to count // the subarray and subsequence of // given length of the array class GFG{ // Function to count the subarray // for the given array static int countSubarray( int n){ return ((n)*(n + 1 ))/ 2 ; } // Function to count the subsequence // for the given array length static int countSubsequence( int n){ return ( int ) Math.pow( 2 , n); } // Driver Code public static void main(String[] args) { int n = 5 ; System.out.print((countSubarray(n)) + "\n" ); System.out.print((countSubsequence(n)) + "\n" ); } } // This code is contributed by Princi Singh |
Python
# Python implementation to count # the subarray and subsequence of # given length of the array # Function to count the subarray # for the given array def countSubarray(n): return ((n) * (n + 1 )) / / 2 # Function to count the subsequence # for the given array length def countSubsequence(n): return ( 2 * * n) # Driver Code if __name__ = = "__main__" : n = 5 print (countSubarray(n)) print (countSubsequence(n)) |
C#
// C# implementation to count // the subarray and subsequence of // given length of the array using System; class GFG{ // Function to count the subarray // for the given array static int countSubarray( int n){ return ((n)*(n + 1))/2; } // Function to count the subsequence // for the given array length static int countSubsequence( int n){ return ( int ) Math.Pow(2, n); } // Driver Code public static void Main(String[] args) { int n = 5; Console.Write((countSubarray(n)) + "\n" ); Console.Write((countSubsequence(n)) + "\n" ); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript implementation to count // the subarray and subsequence of // given length of the array // Function to count the subarray // for the given array function countSubarray(n){ return ((n)*(n + 1))/2; } // Function to count the subsequence // for the given array length function countSubsequence(n){ return Math.pow(2, n); } // Driver Code let n = 5; document.write((countSubarray(n)) + "<br/>" ); document.write((countSubsequence(n)) + "\n" ); </script> |
15 32
Time Complexity: O(log n)
Auxiliary Space: O(1)