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 numbervoid 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 Nvoid 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 Codeint main(){ // Given Number N int N = 4; // Function Call countPermutations(N); return 0;} |
Java
// Java program for// the above approachclass 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 approachmod = 1e9 + 7mx = 1000000fact = [0] * (mx + 1)# Function to calculate the# factorials up to a numberdef 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 Ndef 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 NN = 4# Function callcountPermutations(N)# This code is contributed by code_hunt |
C#
// C# program for// the above approachusing 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> |
Output
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 numberint 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 Nvoid 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 Codeint main(){ // Given Number N int N = 4; // Function Call countPermutations(N); return 0;} |
Java
// Java program for the above approachimport 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
# codemod = 10**9 + 7# Function to calculate the# factorials up to a numberdef 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 Ndef 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 Codeif __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 numberfunction 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 Nfunction 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 Codeconst N = 4;// Function CallcountPermutations(N); |
Output
8 16
Time Complexity: O(N), Where N is the input variable
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
