Number of ways to arrange K different objects taking N objects at a time
Given two integers K and N, the task is to count the number of ways to arrange K different objects taking N objects at a time. Each arrangement contains one object at most once. The answer can be very large so return the answer modulo 109 + 7.
Note: 1 <= N <= K <= 105.
Prerequisites: Factorial of a number, Compute nCr % p
Examples:
Input : N = 3, K = 3
Output : 6
If 1, 2 and 3 be the K different objects, then the possible arrangements are {123, 132, 213, 231, 312, 321}.
Input : N = 4, K = 6
Output : 360
Approach: The problem can be solved using Permutation and Combination. As N is always less than or equal to K, an answer greater than 0 shall always exist. Any object among the K available objects can be used at most once in an arrangement. So, we need to select N objects out of the K available objects for a single arrangement. So, the total number of ways to select N objects from K objects is KCN . Any selected group of N objects can then be permuted among themselves in N ways. So, the answer to the problem is:
(N! * KCN) % (109 +7)
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; #define ll long long #define mod (ll)(1e9 + 7) // Function to return n! % p ll factorial(ll n, ll p) { ll res = 1; // Initialize result for ( int i = 2; i <= n; i++) res = (res * i) % p; return res; } // Iterative Function to calculate (x^y)%p // in O(log y) ll power(ll x, ll y, ll p) { ll res = 1; // Initialize result x = x % p; // Update x if it is more than or // equal to p while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = (res * x) % p; // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res; } // Returns n^(-1) mod p ll modInverse(ll n, ll p) { return power(n, p - 2, p); } // Returns nCr % p using Fermat's little // theorem. ll nCrModP(ll n, ll r, ll p) { // Base case if (r == 0) return 1; // Fill factorial array so that we // can find all factorial of r, n // and n-r ll fac[n + 1]; fac[0] = 1; for ( int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % p; return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p; } // Function to return the number of ways to // arrange K different objects taking N objects // at a time ll countArrangements(ll n, ll k, ll p) { return (factorial(n, p) * nCrModP(k, n, p)) % p; } // Drivers Code int main() { ll N = 5, K = 8; // Function call cout << countArrangements(N, K, mod); return 0; } |
Java
// Java implementation of the approach class GFG { static long mod =( long ) (1e9 + 7 ); // Function to return n! % p static long factorial( long n, long p) { long res = 1 ; // Initialize result for ( int i = 2 ; i <= n; i++) res = (res * i) % p; return res; } // Iterative Function to calculate (x^y)%p // in O(log y) static long power( long x, long y, long p) { long res = 1 ; // Initialize result x = x % p; // Update x if it is more than or // equal to p while (y > 0 ) { // If y is odd, multiply x with result if ((y & 1 )== 1 ) res = (res * x) % p; // y must be even now y = y >> 1 ; // y = y/2 x = (x * x) % p; } return res; } // Returns n^(-1) mod p static long modInverse( long n, long p) { return power(n, p - 2 , p); } // Returns nCr % p using Fermat's little // theorem. static long nCrModP( long n, long r, long p) { // Base case if (r == 0 ) return 1 ; // Fill factorial array so that we // can find all factorial of r, n // and n-r long fac[] = new long [( int )n + 1 ]; fac[ 0 ] = 1 ; for ( int i = 1 ; i <= n; i++) fac[i] = fac[i - 1 ] * i % p; return (fac[( int )n] * modInverse(fac[( int )r], p) % p * modInverse(fac[( int )n - ( int )r], p) % p) % p; } // Function to return the number of ways to // arrange K different objects taking N objects // at a time static long countArrangements( long n, long k, long p) { return (factorial(n, p) * nCrModP(k, n, p)) % p; } // Driver Code public static void main(String[] args) { long N = 5 , K = 8 ; // Function call System.out.println(countArrangements(N, K, mod)); } } /* This code is contributed by PrinciRaj1992 */ |
Python3
# Python3 implementation of the approach mod = 10 * * 9 + 7 # Function to return n! % p def factorial(n, p): res = 1 # Initialize result for i in range ( 2 , n + 1 ): res = (res * i) % p return res # Iterative Function to calculate # (x^y)%p in O(log y) def power(x, y, p): res = 1 # Initialize result x = x % p # Update x if it is # more than or equal to p while (y > 0 ): # If y is odd, # multiply x with result if (y & 1 ): res = (res * x) % p # y must be even now y = y >> 1 # y = y/2 x = (x * x) % p return res # Returns n^(-1) mod p def modInverse(n, p): return power(n, p - 2 , p) # Returns nCr % p using Fermat's little # theorem. def nCrModP(n, r, p): # Base case if (r = = 0 ): return 1 # Fifactorial array so that we # can find afactorial of r, n # and n-r fac = [ 0 for i in range (n + 1 )] fac[ 0 ] = 1 for i in range ( 1 , n + 1 ): fac[i] = fac[i - 1 ] * i % p return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p # Function to return the number of ways # to arrange K different objects taking # N objects at a time def countArrangements(n, k, p): return (factorial(n, p) * nCrModP(k, n, p)) % p # Drivers Code N = 5 K = 8 # Function call print (countArrangements(N, K, mod)) # This code is contributed by mohit kumar |
C#
// C# implementation of the approach using System; class GFG { static long mod =( long ) (1e9 + 7); // Function to return n! % p static long factorial( long n, long p) { long res = 1; // Initialize result for ( int i = 2; i <= n; i++) res = (res * i) % p; return res; } // Iterative Function to calculate (x^y)%p // in O(log y) static long power( long x, long y, long p) { long res = 1; // Initialize result x = x % p; // Update x if it is more than or // equal to p while (y > 0) { // If y is odd, multiply x with result if ((y & 1)==1) res = (res * x) % p; // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res; } // Returns n^(-1) mod p static long modInverse( long n, long p) { return power(n, p - 2, p); } // Returns nCr % p using Fermat's little // theorem. static long nCrModP( long n, long r, long p) { // Base case if (r == 0) return 1; // Fill factorial array so that we // can find all factorial of r, n // and n-r long [] fac = new long [( int )n + 1]; fac[0] = 1; for ( int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % p; return (fac[( int )n] * modInverse(fac[( int )r], p) % p * modInverse(fac[( int )n - ( int )r], p) % p) % p; } // Function to return the number of ways to // arrange K different objects taking N objects // at a time static long countArrangements( long n, long k, long p) { return (factorial(n, p) * nCrModP(k, n, p)) % p; } // Driver Code public static void Main() { long N = 5, K = 8; // Function call Console.WriteLine(countArrangements(N, K, mod)); } } /* This code is contributed by Code_Mech */ |
PHP
<?php // PHP implementation of the approach $mod = (1e9 + 7); // Function to return n! % p function factorial( $n , $p ) { $res = 1; // Initialize result for ( $i = 2; $i <= $n ; $i ++) $res = ( $res * $i ) % $p ; return $res ; } // Iterative Function to calculate (x^y)%p // in O(log y) function power( $x , $y , $p ) { $res = 1; // Initialize result $x = $x % $p ; // Update x if it is more than or // equal to p while ( $y > 0) { // If y is odd, multiply x with result if (( $y & 1)==1) $res = ( $res * $x ) % $p ; // y must be even now $y = $y >> 1; // y = y/2 $x = ( $x * $x ) % $p ; } return $res ; } // Returns n^(-1) mod p function modInverse( $n , $p ) { return power( $n , $p - 2, $p ); } // Returns nCr % p using Fermat's little // theorem. function nCrModP( $n , $r , $p ) { // Base case if ( $r == 0) return 1; // Fill factorial array so that we // can find all factorial of r, n // and n-r $fac = array ((int) $n + 1); $fac [0] = 1; for ( $i = 1; $i <= $n ; $i ++) $fac [ $i ] = $fac [ $i - 1] * $i % $p ; return ( $fac [(int) $n ] * modInverse( $fac [(int) $r ], $p ) % $p * modInverse( $fac [(int) $n - (int) $r ], $p ) % $p ) % $p ; } // Function to return the number of ways to // arrange K different objects taking N objects // at a time function countArrangements( $n , $k , $p ) { return (factorial( $n , $p ) * nCrModP( $k , $n , $p )) % $p ; } // Driver Code { $N = 5; $K = 8; // Function call echo (countArrangements( $N , $K , $mod )); } /* This code is contributed by Code_Mech*/ |
Javascript
<script> // javascript implementation of the approach var mod =parseInt(1e4 + 7); // Function to return n! % p function factorial(n , p) { var res = 1; // Initialize result for ( var i = 2; i <= n; i++) res = (res * i) % p; return res; } // Iterative Function to calculate (x^y)%p // in O(log y) function power(x , y , p) { var res = 1; // Initialize result x = x % p; // Update x if it is more than or // equal to p while (y > 0) { // If y is odd, multiply x with result if ((y & 1)==1) res = (res * x) % p; // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res; } // Returns n^(-1) mod p function modInverse(n , p) { return power(n, p - 2, p); } // Returns nCr % p using Fermat's little // theorem. function nCrModP(n , r , p) { // Base case if (r == 0) return 1; // Fill factorial array so that we // can find all factorial of r, n // and n-r var fac = Array.from({length: n+1}, (_, i) => 0);; fac[0] = 1; for ( var i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % p; return (fac[parseInt(n)] * modInverse(fac[parseInt(r)], p) % p * modInverse(fac[parseInt(n) - parseInt(r)], p) % p) % p; } // Function to return the number of ways to // arrange K different objects taking N objects // at a time function countArrangements(n , k , p) { return (factorial(n, p) * nCrModP(k, n, p)) % p; } // Driver Code var N = 5, K = 8; // Function call document.write(countArrangements(N, K, mod)); // This code contributed by Princi Singh </script> |
6720
Time Complexity: O(n), to fill a factorial array
Auxiliary Space: O(n), extra space of size n used to make a factorial array
Contact Us