Count unimodal and non-unimodal permutations of first N natural numbers
Last Updated :
14 Apr, 2023
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 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 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# 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
<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>
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 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
# 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)
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
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)
Similar Reads
Find the K-th Permutation Sequence of first N natural numbers
Given two integers N and K, find the Kth permutation sequence of numbers from 1 to N without using STL function.Note: Assume that the inputs are such that Kth permutation of N number is always possible. Examples: Input: N = 3, K = 4 Output: 231 Explanation: The ordered list of permutation sequence f
15+ min read
Count array elements that can be maximized by adding any permutation of first N natural numbers
Given an array arr[] consisting of N integers, the task is to determine the total number of array elements that can become the maximum value in the array by adding any permutation of [1, N] to the corresponding value in the given array. Examples: Input: N = 3, arr[] = {8, 9, 6} Output: 2Explanation:
7 min read
Count of subarrays of size K which is a permutation of numbers from 1 to K
Given an array arr of distinct integers, the task is to find the count of sub-arrays of size i having all elements from 1 to i, in other words, the sub-array is any permutation of elements from 1 to i, with 1 < = i <= N. Examples: Input: arr[] = {2, 3, 1, 5, 4} Output: 3 Explanation: we have {
6 min read
Count of distinct permutations of every possible length of given string
Given a string S, the task is to count the distinct permutations of every possible length of the given string. Note: Repetition of characters is not allowed in the string. Input: S = “abcâ€Output: 15Explanation:Possible Permutations of every length are:{“aâ€, “bâ€, “câ€, “abâ€, “bcâ€, “acâ€, “baâ€, “caâ€, “c
5 min read
Iterative program to generate distinct Permutations of a String
Given a string str, the task is to generate all the distinct permutations of the given string iteratively. Examples: Input: str = "bba" Output: abb bab bba Input: str = "abc" Output: abc acb bac bca cab cba Approach: The number of permutations for a string of length n are n!. The following algorithm
15+ min read
Permutations to arrange N persons around a circular table
Given N, the number of persons. The task is to arrange N person around a circular table.Examples: Input: N = 4 Output: 6 Input: N = 5 Output: 24 Approach: It is the concept of Circular permutation i.e. there is no specific starting point in the arrangement, any element can be considered as the start
3 min read
Generate original permutation from given array of inversions
Given an array arr[] of size N, where arr[i] denotes the number of elements on the left that are greater than the ith element in the original permutation. The task is to find the original permutation of [1, N] for which given inversion array arr[] holds valid. Examples: Input: arr[] = {0, 1, 1, 0, 3
14 min read
Count unique subsequences of length K
Given an array of N numbers and an integer K. The task is to print the number of unique subsequences possible of length K. Examples: Input : a[] = {1, 2, 3, 4}, k = 3 Output : 4. Unique Subsequences are: {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4} Input: a[] = {1, 1, 1, 2, 2, 2 }, k = 3 Output : 4 Un
11 min read
Count of contiguous subarrays possible for every index by including the element at that index
Given a number N which represents the size of the array A[], the task is to find the number of contiguous subarrays that can be formed for every index of the array by including the element at that index in the original array. Examples: Input: N = 4 Output: {4, 6, 6, 4} Explanation: Since the size of
8 min read
Count inversions in a permutation of first N natural numbers
Given an array, arr[] of size N denoting a permutation of numbers from 1 to N, the task is to count the number of inversions in the array. Note: Two array elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j. Examples: Input: arr[] = {2, 3, 1, 5, 4}Output: 3Explanation: Given arra
6 min read