Given N, the task is to determine the count of all permutations of size 2N having at least N-increasing elements. An element pi of a permutation P is called increasing if pi < pi+1. For example:
- Permutation [1, 2, 3, 4] will count because the number of such i that pi < pi+1 equals 3 (i = 1, i = 2, i = 3).
- Permutation [3, 2, 1, 4] won’t count, because the number of such i that pi < pi+1 equals 1 (i = 3).
Examples:
Input: 1
Output: 1
Explanation: N = 1, there is only one permutation of size 2 that have at least 1 increasing elements: [1, 2].
In permutation [1, 2], p1 < p2 , and there is one, i=1, that satisfy the condition. Since, 1 ≥ N this permutation should be counted.
In permutation [2, 1], p1 > p2 , and there is no increasing element since, 0<N, this permutation should not be counted.Input: 2
Output: 12
Explanation: N = 2, there are 12 permutations of size 4 that have at least 2 increasing elements. Following are those permutations: [1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [2, 1, 3, 4], [2, 3, 1, 4], [2, 3, 4, 1], [2, 4, 1, 3], [3, 1, 2, 4], [3, 4, 1, 2], [4, 1, 2, 3].
Naive Approach: The basic way to solve the problem is as follows:
Generate all permutations of size 2N and for each permutation check if it is the required permutation by counting the number of increasing elements in it.
Time Complexity: O(N! * N),
- Generating all the permutations of size 2N will take O(N!) time,
- Counting the number of increasing elements in each permutation will take O(N) time
- Thus, overall the naive solution will take O(N! * N) time.
Auxiliary Space: O(N)
Efficient Approach: The problem can be solved based on the following observation:
Assume a permutation P and let k be the total count of increasing elements in P. Assume a permutation Q obtained by reversing permutation P and let l be the total count of increasing elements in Q. Mathematically:
if P = [p1, p2, p3, . . ., p2N], then Q = [p2N, p2N-1, p2N-2, . . ., p2, p1].
k = ∑[pi−1 < pi] ∀ 2⩽ i ⩽ 2NIt can be observed that:
The number of increasing elements in Q = 2N – 1 – Number of increasing elements in P = l = 2N – 1 – kThis means, that for every permutation P having the number of increasing elements k < N, there exists a corresponding permutation Q, obtained by reversing P that has the number of increasing elements l ≥ N.
From the above observation, it can be concluded out of all the permutations of size 2N, exactly half of them will have the count of increasing elements l >= N. Therefore, the count of required permutations = total permutations / 2 = (2N)!/2.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function that returns the count of// all permutations of size 2N having// atleast N increasing elements.int countPermutations(int N){ int ans = 1; // calculate (2N)! for (int i = 1; i <= 2 * N; i++) ans = ans * i; return ans / 2;}// Driver codeint main(){ int N = 2; // Function Call cout << countPermutations(N); return 0;} |
Java
import java.util.*;public class Main { // Function that returns the count of // all permutations of size 2N having // at least N increasing elements. public static int countPermutations(int N) { int ans = 1; // calculate (2N)! for (int i = 1; i <= 2 * N; i++) ans = ans * i; return ans / 2; } //main method public static void main(String[] args) { int N = 2; // Function Call System.out.println(countPermutations(N)); }} |
Python3
# Function that returns the count of# all permutations of size 2N having# atleast N increasing elements.def countPermutations(N): ans = 1 # calculate (2N)! for i in range(1, 2 * N + 1): ans = ans * i return ans // 2# Driver codeN = 2# Function Callprint(countPermutations(N)) |
C#
// C# implementation of the approachusing System;// Function that returns the count of// all permutations of size 2N having// atleast N increasing elements.class MainClass { public static void Main(string[] args) { int N = 2; Console.WriteLine(countPermutations(N)); } public static int countPermutations(int N) { int ans = 1; // calculate (2N)! for (int i = 1; i <= 2 * N; i++) ans = ans * i; return ans / 2; }}// This code is contributed by rambabuguphka |
Javascript
// Function that returns the count of// all permutations of size 2N having// atleast N increasing elements.function countPermutations(N) { let ans = 1; // calculate (2N)! for (let i = 1; i <= 2 * N; i++) { ans = ans * i; } return Math.floor(ans / 2);}// Driver codelet N = 2;// Function Callconsole.log(countPermutations(N));// This code is contributed by Tapesh(tapeshdua420) |
12
Time Complexity: O(N), as we only need to calculate (2N)! which can be calculated in O(N) time
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
