Count unimodal and non-unimodal permutations of first N natural numbers
Given an integer N, the task is to count the total number of unimodal and non-unimodal permutations of integers [1, N] possible.
An unimodal permutation is a permutation which increases up to a certain point following which it starts decreasing.
All other permutations, excluding unimodal permutations, are non-unimodal permutations.
Note: Since the total count can be very large, so print modulo 109+7.
Examples:
Input: N = 3
Output: 4 2
Explanation:
All possible unimodal permutations are {1, 2, 3}, {1, 3, 2}, {2, 3, 1}, {3, 2, 1}.
Therefore, the count of unimodal permutations is 4.
Remaining permutations are {2, 1, 3}, {3, 1, 2}.
Therefore, the count of non-unimodal permutations is 2.Input: N = 4
Output: 8 16
Naive Approach: The simplest approach is to generate all possible permutations of integers from the range [1, N] and then print the count of all those permutations that are unimodal. Print the count of unimodal as well as non-unimodal permutations accordingly.
Time Complexity: O(N!)
Auxiliary Space: O(N)
Efficient Approach: To optimize the above approach, the idea is to first find the total number of unimodal permutations possible for a given integer N and then to find the count of non-unimodal permutations to subtract the count of unimodal permutations from the count of total permutations. Below are the steps:
- Construct unimodal permutations of length N in an infinite length array.
- Place N anywhere in the permutation, then there are exactly two positions at which the (N – 1)th element can be placed, i.e., either to the left or to the right of N.
- Suppose it goes to the right. Now, the (N – 2)th element can be put either to the left or to the right in the current permutation.
- This continues for all elements down to 1. Observe that there are two choices for each element except N.
- So the number of unimodal permutations of length N will be 2N – 1
- The total number of permutations will be N!.
- Now the total number of non-uni modal permutations will be equal to (N! – unimodal permutations).
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; int mod = 1e9 + 7; const int mx = 1e6; int fact[mx + 1]; // Function to calculate the // factorials up to a number void Calculate_factorial() { fact[0] = 1; // Calculate the factorial for ( int i = 1; i <= mx; i++) { fact[i] = i * fact[i - 1]; fact[i] %= mod; } } // Function to find power(a, b) int UniModal_per( int a, int b) { long long int res = 1; // Iterate until b exists while (b) { // If b is divisible by 2 if (b % 2) res = res * a; res %= mod; a = a * a; a %= mod; // Decrease the value of b b /= 2; } // Return the answer return res; } // Function that counts the unimodal // and non-unimodal permutations of // a given integer N void countPermutations( int n) { // Function Call for finding // factorials up to N Calculate_factorial(); // Function to count unimodal // permutations int uni_modal = UniModal_per(2, n - 1); // Non-unimodal permutation is // N! - unimodal permutations int nonuni_modal = fact[n] - uni_modal; cout << uni_modal << " " << nonuni_modal; return ; } // Driver Code int main() { // Given Number N int N = 4; // Function Call countPermutations(N); return 0; } |
Java
// Java program for // the above approach class GFG { static int mod = ( int )(1e9 + 7 ); static int mx = ( int )1e6; static int [] fact = new int [( int )mx + 1 ]; // Function to calculate the // factorials up to a number static void Calculate_factorial() { fact[ 0 ] = 1 ; // Calculate the factorial for ( int i = 1 ; i <= mx; i++) { fact[i] = i * fact[i - 1 ]; fact[i] %= mod; } } // Function to find power(a, b) static int UniModal_per( int a, int b) { int res = 1 ; // Iterate until b exists while (b > 0 ) { // If b is divisible by 2 if (b % 2 != 0 ) res = res * a; res %= mod; a = a * a; a %= mod; // Decrease the value of b b /= 2 ; } // Return the answer return res; } // Function that counts the unimodal // and non-unimodal permutations of // a given integer N static void countPermutations( int n) { // Function Call for finding // factorials up to N Calculate_factorial(); // Function to count unimodal // permutations int uni_modal = UniModal_per( 2 , n - 1 ); // Non-unimodal permutation is // N! - unimodal permutations int nonuni_modal = fact[n] - uni_modal; System.out.print(uni_modal + " " + nonuni_modal); return ; } // Driver Code public static void main(String[] args) { // Given Number N int N = 4 ; // Function Call countPermutations(N); } } // This code is contributed by shikhasingrajput |
Python3
# Python3 program for the above approach mod = 1e9 + 7 mx = 1000000 fact = [ 0 ] * (mx + 1 ) # Function to calculate the # factorials up to a number def Calculate_factorial(): fact[ 0 ] = 1 # Calculate the factorial for i in range ( 1 , mx + 1 ): fact[i] = i * fact[i - 1 ] fact[i] % = mod # Function to find power(a, b) def UniModal_per(a, b): res = 1 # Iterate until b exists while (b ! = 0 ): # If b is divisible by 2 if (b % 2 ! = 0 ): res = res * a res % = mod a = a * a a % = mod # Decrease the value of b b / / = 2 # Return the answer return res # Function that counts the unimodal # and non-unimodal permutations of # a given integer N def countPermutations(n): # Function Call for finding # factorials up to N Calculate_factorial() # Function to count unimodal # permutations uni_modal = UniModal_per( 2 , n - 1 ) # Non-unimodal permutation is # N! - unimodal permutations nonuni_modal = fact[n] - uni_modal print ( int (uni_modal), "", int (nonuni_modal)) return # Driver Code # Given number N N = 4 # Function call countPermutations(N) # This code is contributed by code_hunt |
C#
// C# program for // the above approach using System; class GFG { static int mod = ( int )(1e9 + 7); static int mx = ( int )1e6; static int [] fact = new int [( int )mx + 1]; // Function to calculate the // factorials up to a number static void Calculate_factorial() { fact[0] = 1; // Calculate the factorial for ( int i = 1; i <= mx; i++) { fact[i] = i * fact[i - 1]; fact[i] %= mod; } } // Function to find power(a, b) static int UniModal_per( int a, int b) { int res = 1; // Iterate until b exists while (b > 0) { // If b is divisible by 2 if (b % 2 != 0) res = res * a; res %= mod; a = a * a; a %= mod; // Decrease the value of b b /= 2; } // Return the answer return res; } // Function that counts the unimodal // and non-unimodal permutations of // a given integer N static void countPermutations( int n) { // Function Call for finding // factorials up to N Calculate_factorial(); // Function to count unimodal // permutations int uni_modal = UniModal_per(2, n - 1); // Non-unimodal permutation is // N! - unimodal permutations int nonuni_modal = fact[n] - uni_modal; Console.Write(uni_modal + " " + nonuni_modal); return ; } // Driver Code public static void Main(String[] args) { // Given Number N int N = 4; // Function Call countPermutations(N); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript program for // the above approach var mod = parseInt(1e9 + 7); var mx = 1000000; var fact = new Array(mx + 1).fill(0); // Function to calculate the // factorials up to a number function Calculate_factorial() { fact[0] = 1; // Calculate the factorial for ( var i = 1; i <= mx; i++) { fact[i] = i * fact[i - 1]; fact[i] %= mod; } } // Function to find power(a, b) function UniModal_per(a, b) { var res = 1; // Iterate until b exists while (b > 0) { // If b is divisible by 2 if (b % 2 !== 0) res = res * a; res %= mod; a = a * a; a %= mod; // Decrease the value of b b = parseInt(b / 2); } // Return the answer return res; } // Function that counts the unimodal // and non-unimodal permutations of // a given integer N function countPermutations(n) { // Function Call for finding // factorials up to N Calculate_factorial(); // Function to count unimodal // permutations var uni_modal = UniModal_per(2, n - 1); // Non-unimodal permutation is // N! - unimodal permutations var nonuni_modal = fact[n] - uni_modal; document.write(uni_modal + " " + nonuni_modal); return ; } // Driver Code // Given Number N var N = 4; // Function Call countPermutations(N); </script> |
8 16
Time Complexity: O(N)
Auxiliary Space: O(N)
Efficient approach : Space optimization O(1)
In previous approach we use fact[] to calculate the factorial of n but the we can calculate factorial using variable to optimize space complexity.
Implementation steps:
- The approach is very similar to the previous approach the difference is only in the calculate_factorial.
- Initialize the variable fact with 1.
- Now iterate from 1 to N and get the factorial.
- return the factorial to countPermutations function where we print the uni_model and nonuni_model.
Implementation:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; int mod = 1e9 + 7; // Function to calculate the // factorials up to a number int Calculate_factorial( int n) { int fact = 1; // Calculate the factorial for ( int i = 1; i <= n; i++) { fact = (fact * i) % mod; } return fact; } // Function to find power(a, b) int UniModal_per( int a, int b) { long long int res = 1; // Iterate until b exists while (b) { // If b is divisible by 2 if (b % 2) res = (res * a) % mod; a = (a * a) % mod; // Decrease the value of b b /= 2; } // Return the answer return res; } // Function that counts the unimodal // and non-unimodal permutations of // a given integer N void countPermutations( int n) { // Function Call for finding // factorials up to N int factN = Calculate_factorial(n); // Function to count unimodal // permutations int uni_modal = UniModal_per(2, n - 1); // Non-unimodal permutation is // N! - unimodal permutations int nonuni_modal = factN - uni_modal; cout << uni_modal << " " << nonuni_modal; return ; } // Driver Code int main() { // Given Number N int N = 4; // Function Call countPermutations(N); return 0; } |
Java
// Java program for the above approach import java.util.*; public class Main { static int mod = 1000000007 ; // Function to calculate the factorials up to a number static int Calculate_factorial( int n) { int fact = 1 ; // Calculate the factorial for ( int i = 1 ; i <= n; i++) { fact = ( int )((( long )fact * i) % mod); } return fact; } // Function to find power(a, b) static int UniModal_per( int a, int b) { long res = 1 ; // Iterate until b exists while (b != 0 ) { // If b is divisible by 2 if ((b & 1 ) == 1 ) { res = (res * a) % mod; } a = ( int )((( long )a * a) % mod); // Decrease the value of b b >>= 1 ; } // Return the answer return ( int )res; } // Function that counts the unimodal and non-unimodal // permutations of a given integer N static void countPermutations( int n) { // Function Call for finding factorials up to N int factN = Calculate_factorial(n); // Function to count unimodal permutations int uni_modal = UniModal_per( 2 , n - 1 ); // Non-unimodal permutation is N! - unimodal permutations int nonuni_modal = factN - uni_modal; System.out.println(uni_modal + " " + nonuni_modal); return ; } // Driver Code public static void main(String[] args) { // Given Number N int N = 4 ; // Function Call countPermutations(N); } } // This code is contributed by rishabmalhdijo |
Python3
# code mod = 10 * * 9 + 7 # Function to calculate the # factorials up to a number def Calculate_factorial(n): fact = 1 # Calculate the factorial for i in range ( 1 , n + 1 ): fact = (fact * i) % mod return fact # Function to find power(a, b) def UniModal_per(a, b): res = 1 # Iterate until b exists while b: # If b is divisible by 2 if b % 2 : res = (res * a) % mod a = (a * a) % mod # Decrease the value of b b / / = 2 # Return the answer return res # Function that counts the unimodal # and non-unimodal permutations of # a given integer N def countPermutations(n): # Function Call for finding # factorials up to N factN = Calculate_factorial(n) # Function to count unimodal # permutations uni_modal = UniModal_per( 2 , n - 1 ) # Non-unimodal permutation is # N! - unimodal permutations nonuni_modal = factN - uni_modal print (uni_modal, nonuni_modal) return # Driver Code if __name__ = = '__main__' : # Given Number N N = 4 # Function Call countPermutations(N) |
C#
using System; public class GFG { static int mod = 1000000007; // Function to calculate the // factorials up to a number static int Calculate_factorial( int n) { int fact = 1; // Calculate the factorial for ( int i = 1; i <= n; i++) { fact = (fact * i) % mod; } return fact; } // Function to find power(a, b) static int UniModal_per( int a, int b) { long res = 1; // Iterate until b exists while (b > 0) { // If b is divisible by 2 if (b % 2 == 1) res = (res * a) % mod; a = (a * a) % mod; // Decrease the value of b b /= 2; } // Return the answer return ( int )res; } // Function that counts the unimodal // and non-unimodal permutations of // a given integer N static void countPermutations( int n) { // Function Call for finding // factorials up to N int factN = Calculate_factorial(n); // Function to count unimodal // permutations int uni_modal = UniModal_per(2, n - 1); // Non-unimodal permutation is // N! - unimodal permutations int nonuni_modal = factN - uni_modal; Console.WriteLine(uni_modal + " " + nonuni_modal); return ; } // Driver Code public static void Main() { // Given Number N int N = 4; // Function Call countPermutations(N); } } // This code is contributed by sarojmcy2e |
Javascript
const mod = 1000000007; // Function to calculate the factorials up to a number function calculateFactorial(n) { let fact = 1; // Calculate the factorial for (let i = 1; i <= n; i++) { fact = (fact * i) % mod; } return fact; } // Function to find power(a, b) function unimodalPer(a, b) { let res = 1; // Iterate until b exists while (b !== 0) { // If b is divisible by 2 if ((b & 1) === 1) { res = (res * a) % mod; } a = (a * a) % mod; // Decrease the value of b b >>= 1; } // Return the answer return res; } // Function that counts the unimodal and non-unimodal permutations // of a given integer N function countPermutations(n) { // Function Call for finding factorials up to N const factN = calculateFactorial(n); // Function to count unimodal permutations const uni_modal = unimodalPer(2, n - 1); // Non-unimodal permutation is N! - unimodal permutations const nonuni_modal = factN - uni_modal; console.log(`${uni_modal} ${nonuni_modal}`); } // Driver Code const N = 4; // Function Call countPermutations(N); |
Output
8 16
Time Complexity: O(N), Where N is the input variable
Auxiliary Space: O(1)
Contact Us