Given two values N and K. Find the number of ways to arrange the N distinct items in the boxes such that exactly K (K<N) boxes are used from the N distinct boxes. 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 = 5, k = 5
Output: 120Input: N = 5, k = 3
Output: 1500
Approach: We will use the inclusion-exclusion principle to count the ways.
- Let us assume that the boxes are numbered 1 to N and now we have to choose any K boxes and use them. The number of ways to do this is NCK.
- Now any item can be put in any of the chosen boxes, hence the number of ways to arrange them is KN But here, we may count arrangements with some boxes empty. Hence, we will use the inclusion-exclusion principle to ensure that we count ways with all K boxes filled with at least one item.
- Let us understand the application of the inclusion-exclusion principle:
- So out of KN ways, we subtract the case when at least 1 box(out of K) is empty. Hence, subtract
(KC1)*((K-1)N). - Note that here, The cases where exactly two boxes are empty are subtracted twice(once when we choose the first element in (KC1) ways, and then when we choose the second element in (KC1) ways).
- Hence, we add these ways one time to compensate. So we add (KC2)*((K – 2)N).
- Similarly, here we need to add the number of ways when at least 3 boxes were empty, and so on…
- So out of KN ways, we subtract the case when at least 1 box(out of K) is empty. Hence, subtract
- Hence, the total number of ways:
C++
// C++ program to calculate the // above formula#include <bits/stdc++.h>#define mod 1000000007#define int long longusing namespace std;// To store the factorials // of all numbersint factorial[100005];// Function to calculate factorial // of all numbersvoid StoreFactorials(int n){ factorial[0] = 1; for (int i = 1; i <= n; i++) { factorial[i] = (i * factorial[i - 1]) % mod; }}// Calculate x to the power y // in O(log n) timeint Power(int x, int y){ int ans = 1; while (y > 0) { if (y % 2 == 1) { ans = (ans * x) % mod; } x = (x * x) % mod; y /= 2; } return ans;}// Function to find inverse mod of // a number xint invmod(int x){ return Power(x, mod - 2);}// Calculate (n C r)int nCr(int n, int r){ return (factorial[n] * invmod((factorial[r] * factorial[n - r]) % mod)) % mod;}int CountWays(int n,int k){ StoreFactorials(n); // Loop to compute the formula // evaluated int ans = 0; for (int i = k; i >= 0; i--) { if (i % 2 == k % 2) { // Add even power terms ans = (ans + (Power(i, n) * nCr(k, i)) % mod) % mod; } else { // Subtract odd power terms ans = (ans + mod - (Power(i, n) * nCr(k, i)) % mod) % mod; } } // Choose the k boxes which // were used ans = (ans * nCr(n, k)) % mod; return ans;}// Driver codesigned main(){ int N = 5; int K = 5; cout << CountWays(N, K) << "\n"; return 0;} |
Java
// Java program to calculate the // above formula import java.util.*; class GFG{ static long mod = 1000000007;// To store the factorials // of all numbersstatic long factorial[] = new long[100005];// Function to calculate factorial // of all numbersstatic void StoreFactorials(int n){ factorial[0] = 1; for(int i = 1; i <= n; i++) { factorial[i] = (i * factorial[i - 1]) % mod; }}// Calculate x to the power y // in O(log n) timestatic long Power(long x, long y){ long ans = 1; while (y > 0) { if (y % 2 == 1) { ans = (ans * x) % mod; } x = (x * x) % mod; y /= 2; } return ans;}// Function to find inverse mod of // a number xstatic long invmod(long x){ return Power(x, mod - 2);}// Calculate (n C r)static long nCr(int n, int r){ return (factorial[n] * invmod((factorial[r] * factorial[n - r]) % mod)) % mod;}static long CountWays(int n,int k){ StoreFactorials(n); // Loop to compute the formula // evaluated long ans = 0; for(int i = k; i >= 0; i--) { if (i % 2 == k % 2) { // Add even power terms ans = (ans + (Power(i, n) * nCr(k, i)) % mod) % mod; } else { // Subtract odd power terms ans = (ans + mod - (Power(i, n) * nCr(k, i)) % mod) % mod; } } // Choose the k boxes which // were used ans = (ans * nCr(n, k)) % mod; return ans;} // Driver Code public static void main (String[] args){ int N = 5; int K = 5; System.out.print(CountWays(N, K) + "\n");} }// This code is contributed by math_lover |
Python3
# Python3 program to calculate the # above formulamod = 1000000007# To store the factorials # of all numbersfactorial = [0 for i in range(100005)]# Function to calculate factorial # of all numbersdef StoreFactorials(n): factorial[0] = 1 for i in range(1, n + 1, 1): factorial[i] = (i * factorial[i - 1]) % mod# Calculate x to the power y # in O(log n) timedef Power(x, y): ans = 1 while (y > 0): if (y % 2 == 1): ans = (ans * x) % mod x = (x * x) % mod y //= 2 return ans# Function to find inverse mod # of a number xdef invmod(x): return Power(x, mod - 2)# Calculate (n C r)def nCr(n, r): return ((factorial[n] * invmod((factorial[r] * factorial[n - r]) % mod)) % mod)def CountWays(n, k): StoreFactorials(n) # Loop to compute the formula # evaluated ans = 0 i = k while(i >= 0): if (i % 2 == k % 2): # Add even power terms ans = ((ans + (Power(i, n) * nCr(k, i)) % mod) % mod) else: # Subtract odd power terms ans = ((ans + mod - (Power(i, n) * nCr(k, i)) % mod) % mod) i -= 1 # Choose the k boxes which # were used ans = (ans * nCr(n, k)) % mod return ans# Driver codeif __name__ == '__main__': N = 5 K = 5 print(CountWays(N, K))# This code is contributed by Surendra_Gangwar |
C#
// C# program to calculate the // above formula using System; using System.Collections;using System.Collections.Generic; class GFG{ static long mod = 1000000007;// To store the factorials // of all numbersstatic long []factorial = new long[100005];// Function to calculate factorial // of all numbersstatic void StoreFactorials(int n){ factorial[0] = 1; for(int i = 1; i <= n; i++) { factorial[i] = (i * factorial[i - 1]) % mod; }}// Calculate x to the power y // in O(log n) timestatic long Power(long x, long y){ long ans = 1; while (y > 0) { if (y % 2 == 1) { ans = (ans * x) % mod; } x = (x * x) % mod; y /= 2; } return ans;}// Function to find inverse mod of // a number xstatic long invmod(long x){ return Power(x, mod - 2);}// Calculate (n C r)static long nCr(int n, int r){ return (factorial[n] * invmod((factorial[r] * factorial[n - r]) % mod)) % mod;}static long CountWays(int n,int k){ StoreFactorials(n); // Loop to compute the formula // evaluated long ans = 0; for(int i = k; i >= 0; i--) { if (i % 2 == k % 2) { // Add even power terms ans = (ans + (Power(i, n) * nCr(k, i)) % mod) % mod; } else { // Subtract odd power terms ans = (ans + mod - (Power(i, n) * nCr(k, i)) % mod) % mod; } } // Choose the k boxes which // were used ans = (ans * nCr(n, k)) % mod; return ans;} // Driver Code public static void Main (string[] args){ int N = 5; int K = 5; Console.Write(CountWays(N, K) + "\n");} }// This code is contributed by rutvik_56 |
Javascript
<script> let mod = 1000000007; let factorial = [] function StoreFactorials(n){ factorial[0] = 1; for(let i = 1; i <= n; i++){ factorial[i] = (i * factorial[i - 1]) % mod; } } // Calculate x to the power y in O(log n) time function Power(x, y){ var ans = 1; while(y > 0){ if(y % 2 == 1){ ans = (ans * x) % mod; } x = (x * x) % mod; y /= 2; } return ans; } // Function to find inverse mod of a number x function invmod(x){ return Power(x, mod-2); } // Calculate (nCr) function nCr(n, r){ return (factorial[n] * invmod((factorial[r] * factorial[n - r]) % mod)) % mod; } function CountWays(n, k){ StoreFactorials(n); // Loop to compute the formula evaluated var ans = 0; for(let i = k; i >= 0; i--) { if (i % 2 == k % 2) { // Add even power terms ans = (ans + (Power(i, n) * nCr(k, i)) % mod) % mod; } else { // Subtract odd power terms ans = (ans + mod - (Power(i, n) * nCr(k, i)) % mod) % mod; } } // Choose the k boxes which // were used ans = (ans * nCr(n, k)) % mod; return ans; } var N = 5; var K = 5; document.write(CountWays(N, K)); // This code is contributed by lokeshmvs21.</script> |
Output:
120
Time complexity: O(N*log N)
Auxiliary Space: O(105)
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!
