Count possible combinations of pairs with adjacent elements from first N numbers
Given a number N, the task is to count all possible combinations of pairs formed using adjacent elements.
Note: If an element exists already in a pair, it cannot be picked in the next pair. For example: for {1,2,3}: {1,2} and {2,3} will not be considered as a correct combination.
Examples:
Input : N = 4 Output : 5 Explanation : If N = 4, the possible combinations are: {1}, {2}, {3}, {4} {1, 2}, {3, 4} {1}, {2, 3}, {4} {1}, {2}, {3, 4} {1, 2}, {3}, {4} Input : N = 5 Output : 8
Approach : Break the problem into smaller subproblems. If there are N numbers, and there are two cases either a number is alone, or it is in a pair, if a number is alone, find the ways of pairing (n-1) numbers left, or if it is in a pair, find the ways of pairing (n-2) numbers left. If there are just 2 numbers left they can generate 2 combinations either alone or in a pair, and if a single number is left it will be in singleton, so there is just 1 combination.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Function to count the number of ways int ways( int n) { // If there is a single number left // it will form singleton if (n == 1) { return 1; } // if there are just 2 numbers left, // they will form a pair if (n == 2) { return 2; } else { return ways(n - 1) + ways(n - 2); } } // Driver Code int main() { int n = 5; cout << "Number of ways = " << ways(n); return 0; } |
Java
/*package whatever //do not write package name here */ import java.io.*; class GFG { // Function to count the number of ways static int ways( int n) { // If there is a single number left // it will form singleton if (n == 1 ) { return 1 ; } // if there are just 2 numbers left, // they will form a pair if (n == 2 ) { return 2 ; } else { return ways(n - 1 ) + ways(n - 2 ); } } // Driver Code public static void main (String[] args) { int n = 5 ; System.out.println( "Number of ways = " + ways(n)); } } |
Python3
# Python3 code implementation of the above program # Function to count the number of ways def ways(n) : # If there is a single number left # it will form singleton if (n = = 1 ) : return 1 ; # if there are just 2 numbers left, # they will form a pair if (n = = 2 ) : return 2 ; else : return ways(n - 1 ) + ways(n - 2 ); # Driver Code if __name__ = = "__main__" : n = 5 ; print ( "Number of ways = " , ways(n)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the above code using System; class GFG { // Function to count the number of ways static int ways( int n) { // If there is a single number left // it will form singleton if (n == 1) { return 1; } // if there are just 2 numbers left, // they will form a pair if (n == 2) { return 2; } else { return ways(n - 1) + ways(n - 2); } } // Driver Code public static void Main() { int n = 5; Console.WriteLine( "Number of ways = " + ways(n)); } } // This code is contributed by AnkitRai01 |
Javascript
<script> // Javascript implementation of the above code // Function to count the number of ways function ways(n) { // If there is a single number left // it will form singleton if (n == 1) { return 1; } // if there are just 2 numbers left, // they will form a pair if (n == 2) { return 2; } else { return ways(n - 1) + ways(n - 2); } } let n = 5; document.write( "Number of ways = " + ways(n)); // This code is contributed by suresh07. </script> |
Number of ways = 8
Time Complexity: O(2^N)
Auxiliary Space: O(N)
Another Approach:
We can store the computed values in an array and reuse the computed value afterwords which would make the program efficient.
Implementation of the above approach:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; // vector to store the computed values vector< int > dp; // Function to count the number of ways int ways( int n) { // If there is a single number left // it will form singleton int & res = dp[n]; // return the stored value // if the value is already computed if (res!=-1) return res; // base case if (n == 1) { return res=1; } // if there are just 2 numbers left, // they will form a pair if (n == 2) { return res=2; } else { return res = ways(n - 1) + ways(n - 2); } } // Driver Code int main() { int n = 5; dp = vector< int >(n + 1,-1); cout << "Number of ways = " << ways(n); return 0; } |
Java
// Java implementation of the above approach class GFG { // vector to store the computed values static int [] dp; // Function to count the number of ways static int ways( int n) { // If there is a single number left // it will form singleton int res = dp[n]; // return the stored value // if the value is already computed if (res != - 1 ) return res; // base case if (n == 1 ) { return res = 1 ; } // if there are just 2 numbers left, // they will form a pair if (n == 2 ) { return res = 2 ; } else { return res = ways(n - 1 ) + ways(n - 2 ); } } // Driver Code public static void main(String[] args) { int n = 10 ; dp = new int [n + 1 ]; Arrays.fill(dp, - 1 ); System.out.println( "Number of ways = " + ways(n)); } } // This code is contributed by jainlovely450 |
Python3
# Python3 implementation of the above approach # vector to store the computed values dp = [] # Function to count the number of ways def ways(n): # If there is a single number left # it will form singleton res = dp[n] # return the stored value # if the value is already computed if (res! = - 1 ): return res # base case if (n = = 1 ) : res = 1 return res # if there are just 2 numbers left, # they will form a pair if (n = = 2 ) : res = 2 return res else : res = ways(n - 1 ) + ways(n - 2 ) return res # Driver Code if __name__ = = '__main__' : n = 5 dp = [ - 1 ] * (n + 1 ) print ( "Number of ways =" ,ways(n)) |
C#
using System; class Program { // vector to store the computed values static int [] dp; // Function to count the number of ways static int Ways( int n) { // If there is a single number left // it will form singleton int res = dp[n]; // return the stored value // if the value is already computed if (res!=-1) { return res; } // base case if (n == 1) { res=1; return res; } // if there are just 2 numbers left, // they will form a pair if (n == 2) { res=2; return res; } else { res = Ways(n - 1) + Ways(n - 2); return res; } } // Derive code static void Main( string [] args) { int n = 5; dp = new int [n + 1]; for ( int i = 0; i <= n; i++) { dp[i] = -1; } Console.WriteLine( "Number of ways = " + Ways(n)); } } // This code is contributed by shiv1o43g |
Javascript
<script> // JavaScript implementation of the above approach // array to store the computed values let dp = []; // Function to count the number of ways function ways(n) { // If there is a single number left // it will form singleton let res = dp[n]; // return the stored value // if the value is already computed if (res!=-1) return res; // base case if (n == 1) { res = 1; return res; } // if there are just 2 numbers left, // they will form a pair if (n == 2) { res = 2; } else { res = ways(n - 1) + ways(n - 2); } dp[n] = res; return res; } // Driver Code let n = 5; dp = new Array(n+1).fill(-1); document.write(dp); document.write( "Number of ways = " + ways(n)); // This code is contributed by shinjanpatra </script> |
Number of ways = 8
Time Complexity: O(n)
Auxiliary Space: O(n)
Contact Us