Horje
Count arrangements of N people around circular table such that K people always sit together

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. 

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 number
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
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 
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 approach
 
import 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 approach
 
mod = 1000000007
 
# Function to compute factorial of a number
def fac(f):
    fac = 1
    for i in range(2, f + 1):
        fac = (fac * i) % mod
    return fac   
 
# Function to find number of ways
def Ways(n, k):
    # Find (n-k) factorial and k factorial
    # Return product of these two
    return (fac(n - k) * fac(k)) % mod
 
   
# Driver code
if __name__ == '__main__':
    N = 8
    K = 3
    print(Ways(N, K));

C#

// C# code to implement the above approach
using 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 approach
 
 
let mod = 1000000007;
 
// Function to compute factorial of a number
function fac(f) {
  let fac = 1;
  for (let i = 1; i <= f; i++)
    fac = (fac * i) % mod;
  return fac;
}
 
// Function to find number of ways
function 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>

Output

720

Time Complexity: O(N)
Auxiliary Space: O(1)


 


Reffered: https://www.geeksforgeeks.org

Mathematical

Related
Squarable Numbers Squarable Numbers
Maximum cells attacked by Rook or Bishop in given Chessboard Maximum cells attacked by Rook or Bishop in given Chessboard
Check if Array can be generated where no element is Geometric mean of neighbours Check if Array can be generated where no element is Geometric mean of neighbours
Minimum divisions to reduce N to 1 by following given conditions Minimum divisions to reduce N to 1 by following given conditions
Minimum cost to convert 1 to N by multiplying X or right rotation of digits Minimum cost to convert 1 to N by multiplying X or right rotation of digits

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 15



 

Horje