Given N students and a total of M sets of question paper where M ? N. All the M sets are different and every sets is available in sufficient quantity. All the students are sitting in a single row. The task is to find the number of ways to distribute the question paper so that if any M consecutive students are selected then each student has a unique question paper set. The answer could be large, so print the answer modulo 109 + 7.
Example:
Input: N = 2, M = 2
Output: 2
(A, B) and (B, A) are the only possible ways.
Input: N = 15, M = 4
Output: 24
Approach: It can be observed that the number of ways are independent of N and only depend on M. First M students can be given M sets and then the same pattern can be repeated. The number of ways to distribute the question paper in this way is M!. For example,
N = 6, M = 3
A, B, C, A, B, C
A, C, B, A, C, B
B, C, A, B, C, A
B, A, C, B, A, C
C, A, B, C, A, B
C, B, A, C, B, A
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;const int MOD = 1000000007;// Function to return n! % 1000000007int factMod(int n){ // To store the factorial long fact = 1; // Find the factorial for (int i = 2; i <= n; i++) { fact *= (i % MOD); fact %= MOD; } return fact;}// Function to return the// count of possible waysint countWays(int n, int m){ return factMod(m);}// Driver codeint main(){ int n = 2, m = 2; cout << countWays(n, m); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{static int MOD = 1000000007;// Function to return n! % 1000000007static int factMod(int n){ // To store the factorial long fact = 1; // Find the factorial for (int i = 2; i <= n; i++) { fact *= (i % MOD); fact %= MOD; } return (int)fact;}// Function to return the// count of possible waysstatic int countWays(int n, int m){ return factMod(m);}// Driver codepublic static void main(String args[]){ int n = 2, m = 2; System.out.print(countWays(n, m));}}// This code is contributed by Arnab Kundu |
Python3
# Python3 implementation of the approach MOD = 1000000007; # Function to return n! % 1000000007 def factMod(n) : # To store the factorial fact = 1; # Find the factorial for i in range(2, n + 1) : fact *= (i % MOD); fact %= MOD; return fact; # Function to return the # count of possible ways def countWays(n, m) : return factMod(m);# Driver code if __name__ == "__main__" : n = 2; m = 2; print(countWays(n, m));# This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System;class GFG{ static int MOD = 1000000007; // Function to return n! % 1000000007 static int factMod(int n) { // To store the factorial int fact = 1; // Find the factorial for (int i = 2; i <= n; i++) { fact *= (i % MOD); fact %= MOD; } return fact; } // Function to return the // count of possible ways static int countWays(int n, int m) { return factMod(m); } // Driver code public static void Main() { int n = 2, m = 2; Console.Write(countWays(n, m)); } }// This code is contributed by Sanjit Prasad |
Javascript
<script>// javascript implementation of the approach MOD = 1000000007; // Function to return n! % 1000000007 function factMod(n) { // To store the factorial var fact = 1; // Find the factorial for (i = 2; i <= n; i++) { fact *= (i % MOD); fact %= MOD; } return parseInt( fact); } // Function to return the // count of possible ways function countWays(n , m) { return factMod(m); } // Driver code var n = 2, m = 2; document.write(countWays(n, m));// This code contributed by aashish1995</script> |
2
Time Complexity: O(n)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
