Given integers N and K, the task is to find the number of possible arrangements of N people around a circular table such that K people always sit together.
Note: As the answer can be very large return it modulo 109 + 7
Examples:
Input: N = 4, K = 3
Output: 6
Explanation: If 3 people always sit together (say 1, 2 and 3) then the possible arrangements can be
{1, 2, 3, 4}, {1, 3, 2, 4}, {2, 1, 3, 4}, {2, 3, 1, 4}, {3, 2, 1, 4}, {3, 1, 2, 4}.
As there is no start or end in a circular arrangement and
the arrangements are based on relative positions, so we can consider
4 is always fixed in the last position.Input: N = 8, K = 3
Output: 720
Approach: This problem can be solved based on the following mathematical idea:
In a circular arrangement there is no starting or ending and the arrangements are based on relative positions.
So it can be considered that any one of the person is always sitting in a fixed position and all other positions are relative to that position.
So total possible arrangements of N people around a circular table is (N-1)!As K people will always sit together, they can be considered a group or as a single unit.
So total unit now X = (N – K + 1). Total possible arrangements of these many people are:
(X – 1)! = (N – K)!The people of this single group can be arranged in K! ways for each of the possible arrangements.
therefore total possible arrangements = K! * (N – K)!
Follow the below steps to implement the above approach.
- Calculate the factorial of K.
- Calculate the factorial of (N – K).
- Multiply these two values to get the actual answer.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <iostream>using namespace std;const int mod = 1000000007;// Function to compute factorial of a numberint fac(int f) { int fac = 1; for (int i = 1; i <= f; i++) fac = (fac * i) % mod; return fac;}// Function to find number of waysint Ways(int n, int k) { // Find (n-k) factorial and k factorial // Return product of these two return (fac(n - k) * fac(k)) % mod;} // Driver code int main() { int N = 8; int K = 3; cout << Ways(N, K); return 0;}// This code is contributed by ANKITKUMAR34. |
Java
// Java code for the above approachimport java.io.*;class GFG { static int mod = 1000000007; // Function to compute factorial of a number static int fac(int f) { int fac = 1; for (int i = 1; i <= f; i++) fac = (fac * i) % mod; return fac; } // Function to find number of ways static int Ways(int n, int k) { // Find (n-k) factorial and k factorial // Return product of these two return (fac(n - k) * fac(k)) % mod; } public static void main(String[] args) { int N = 8; int K = 3; System.out.println(Ways(N, K)); }}// This code is contributed by Potta Lokesh |
Python3
# Python code to implement the approachmod = 1000000007# Function to compute factorial of a numberdef fac(f): fac = 1 for i in range(2, f + 1): fac = (fac * i) % mod return fac # Function to find number of waysdef Ways(n, k): # Find (n-k) factorial and k factorial # Return product of these two return (fac(n - k) * fac(k)) % mod # Driver codeif __name__ == '__main__': N = 8 K = 3 print(Ways(N, K)); |
C#
// C# code to implement the above approachusing System;public class GFG{ static int mod = 1000000007; // Function to compute factorial of a number static int fac(int f) { int fac = 1; for (int i = 1; i <= f; i++) fac = (fac * i) % mod; return fac; } // Function to find number of ways static int Ways(int n, int k) { // Find (n-k) factorial and k factorial // Return product of these two return (fac(n - k) * fac(k)) % mod; } // Driver code static public void Main (){ int N = 8; int K = 3; Console.WriteLine(Ways(N, K)); }}// This code is contributed by AnkThon |
Javascript
<script>// Javascript code to implement the approachlet mod = 1000000007;// Function to compute factorial of a numberfunction fac(f) { let fac = 1; for (let i = 1; i <= f; i++) fac = (fac * i) % mod; return fac;}// Function to find number of waysfunction Ways(n, k) { // Find (n-k) factorial and k factorial // Return product of these two return (fac(n - k) * fac(k)) % mod;}// Driver code let N = 8;let K = 3;document.write(Ways(N, K))// This code is contributed by Saurabh Jaiswal</script> |
720
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!
