Given an integer N, the task is to find the number of permutations of integers from the range [1, N] that can form an acyclic graph according to the following conditions:
- For every 1 ? i ? N, find the largest j such that 1 ? j < i and A[j] > A[i], and add an undirected edge between node i and node j.
- For every 1 ? i ? N, find the smallest j such that i < j ? N and A[j] > A[i], and add an undirected edge between node i and node j.
Examples:
Input: 3
Output: 4
Explanation:
{1, 2, 3}: Possible (Graph Edges : { [1, 2], [2, 3] }. Therefore, no cycle exists)
{1, 3, 2}: Possible (Graph Edges : { [1, 3], [2, 3] }. Therefore, no cycle exists)
{2, 1, 3}: Not possible (Graph Edges : { [2, 3], [1, 3], [1, 2] }. Therefore, cycle exists)
{2, 3, 1}: Possible (Graph Edges : { [2, 3], [1, 3] }. Therefore, no cycle exists)
{3, 1, 2}: Not possible (Graph Edges : { [1, 2], [1, 3], [2, 3] }. Therefore, cycle exists)
{3, 2, 1}: Possible (Graph Edges : { [2, 3], [1, 2] }. Therefore, no cycle exists)Input : 4
Output : 8
Approach: Follow the steps below to solve the problem:
- There are a total of N! possible arrays that can be generated consisting of permutations of integers from the range [1, N].
- According to the given conditions, if i, j, k (i < j < k) are indices from the array, then if A[i] > A[j] and A[j] < A[k], then there will be a cycle consisting of edges {[A[j], A[i]], [A[j], A[k]], [A[i], A[k]]}.
- Removing these permutations, there are 2(N – 1) possible permutations remaining.
- Remaining permutations gives only two possible positions for integers from the range [1, N – 1] and 1 possible position for N.
Illustration:
For N = 3:
Permutation {2, 1, 3} contains a cycle as A[0] > A[1] and A[1] < A[2].
Permutation {3, 1, 2} contains a cycle as A[0] > A[1] and A[1] < A[2].
All remaining permutations can generate an acyclic graph.
Therefore, the count of valid permutations = 3! – 2 = 4 = 23 – 1
- Therefore, print 2N – 1 as the required answer.
Below is the implementation of the above approach :
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Find the count of possible graphs void possibleAcyclicGraph( int N) { cout << pow (2, N - 1); return ; } // Driver Code int main() { int N = 4; possibleAcyclicGraph(N); return 0; } |
Java
// Java implementation of // the above approach import java.util.*; class GFG{ // Find the count of // possible graphs static void possibleAcyclicGraph( int N) { System.out.print(( int )Math.pow( 2 , N - 1 )); return ; } // Driver Code public static void main(String[] args) { int N = 4 ; possibleAcyclicGraph(N); } } // This code is contributed by Princi Singh |
Python3
# Python3 implementation of above approach # Find the count of possible graphs def possibleAcyclicGraph(N): print ( pow ( 2 , N - 1 )) return # Driver code if __name__ = = '__main__' : N = 4 possibleAcyclicGraph(N) # This code is contributed by mohit kumar 29 |
C#
// C# implementation of // the above approach using System; class GFG{ // Find the count of // possible graphs static void possibleAcyclicGraph( int N) { Console.Write(( int )Math.Pow(2, N - 1)); return ; } // Driver Code public static void Main() { int N = 4; possibleAcyclicGraph(N); } } // This code is contributed by sanjoy_62 |
Javascript
<script> // Javascript implementation of above approach // Find the count of // possible graphs function possibleAcyclicGraph(N) { document.write(Math.pow(2, N - 1)); return ; } // Driver Code let N = 4; possibleAcyclicGraph(N); // This code is contributed by target_2 </script> |
8
Time Complexity: O(logN)
Space Complexity: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!