Given n and m, the task is to find the number of permutations of n distinct things taking them all at a time such that m particular things never come together.
Examples:
Input : 7, 3 Output : 420 Input : 9, 2 Output : 282240
Approach:
Derivation of the formula –
Total number of arrangements possible using n distinct objects taking all at a time = 
Number of arrangements of n distinct things taking all at a time, when m particular things always come together, is 
Hence, the number of permutations of 
distinct things taking all at a time, when 
particular things never come together –
Permutations = n! - (n-m+1)! × m!
Below is the implementation of above approach –
C++
#include<bits/stdc++.h>using namespace std;int factorial(int n){ int fact = 1; for (int i = 2; i <= n; i++) fact = fact * i ; return (fact);}int result(int n, int m){ return(factorial(n) - factorial(n - m + 1) * factorial(m));}// Driver Codeint main(){ cout(result(5, 3));}// This code is contributed by Mohit Kumar |
Java
class GFG{static int factorial(int n){ int fact = 1; for (int i = 2; i <= n; i++) fact = fact * i ; return (fact);}static int result(int n, int m){ return(factorial(n) - factorial(n - m + 1) * factorial(m));}// Driver Codepublic static void main(String args[]){ System.out.println(result(5, 3));}}// This code is contributed by Arnab Kundu |
Python3
def factorial(n): fact = 1; for i in range(2, n + 1): fact = fact * i return (fact) def result(n, m): return(factorial(n) - factorial(n - m + 1) * factorial(m))# driver codeprint(result(5, 3)) |
C#
using System;class GFG { static int factorial(int n) { int fact = 1; for (int i = 2; i <= n; i++) fact = fact * i ; return (fact); } static int result(int n, int m) { return(factorial(n) - factorial(n - m + 1) * factorial(m)); } // Driver Code public static void Main() { Console.WriteLine(result(5, 3)); } }// This code is contributed by AnkitRai01 |
Javascript
<script>// Below is the JavaScript implementation of above approach function factorial(n) { let fact = 1; for (let i = 2; i <= n; i++) fact = fact * i ; return (fact); } function result(n, m) { return(factorial(n) - factorial(n - m + 1) * factorial(m)); } // Driver Code document.write(result(5, 3)); // This code is contributed by Surbhi Tyagi.</script> |
Output :
84
Time Complexity: O(n)
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!