Count unimodal and non-unimodal permutations of first N natural numbers

0 0 11 minutes read

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 10⁹+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 2^{N – 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>

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 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)

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 zambiatek!