Number of Ways to Handshakes That Don’t Cross
Given an even number of people n, who are standing in a circle. Each person shakes hands with one other person, resulting in a total of n/2 handshakes. The task is to find the number of ways these handshakes can occur such that none of the handshakes cross. Since the answer could be very large, you need to return the result modulo 10^9 + 7.
Example:
Input: n = 4
Output: 2
Explanation: There are two ways to do it, the first way is [(1,2),(3,4)] and the second one is [(2,3),(4,1)].Input: n = 6
Output: 5
Approach:
The idea behind the solution is to use a dynamic programming array dp, where dp[i] represents the number of ways to arrange i people in a circle without any handshakes crossing. The base case is straightforward: dp[0] is 1, as there is exactly one way to arrange zero people (an empty arrangement). For each even number i from 2 to n, considers different possible positions for the first person to shake hands, effectively dividing the problem into smaller subproblems. For each position j, calculates the number of ways to arrange the remaining people on either side of the handshake. The results are combined, taking into account symmetry (clockwise and counterclockwise arrangements). By iterating through all possible configurations and combining the results using modular arithmetic to handle large numbers, builds up the solution incrementally.
Steps-by-step appraoch:
- Loop through i (number of people, starting from 2, increment by 2).
- For each i:
- Loop through j (possible positions for first person, increment by 2).
- Calculate dp[i] based on j:
- If j is last person, add dp[j] * dp[i-j-2] % mod.
- Otherwise, add 2 * (dp[j] % mod) * (dp[i-j-2] % mod) % mod.
- Return dp[n] (number of ways for n).
Below is the implementation of the above approach:
#include <iostream>
#include <vector>
using namespace std;
// Function to calculate the number of ways to arrange the
// people in a circle
int numberOfWays(int n)
{
// Handle invalid input (number of people cannot be
// negative)
if (n < 0) {
return 0;
}
const int mod
= 1e9 + 7; // Modulo value to handle large numbers
// dp[i] stores the number of ways to arrange i people
// in a circle
vector<long> dp(n + 1, 0);
// Base case: 0 people can be arranged in 1 way (empty
// circle)
dp[0] = 1;
// Loop through number of people (starting from 2, as 0
// and 1 are handled)
for (int i = 2; i <= n; i += 2) {
// Loop through possible positions for the first
// person (from 0 to i-2)
for (int j = 0; j <= i - j - 2; j += 2) {
// If j is the last person (i-j-2), there's only
// one way to arrange the remaining
if (j == i - j - 2) {
dp[i] += (dp[j] * dp[i - j - 2]) % mod;
}
else {
// Otherwise, add the number of arrangements
// where the first j people form a group and
// the remaining i-j-2 people form a group,
// multiplied by 2 (since the arrangement
// can be clockwise or counter-clockwise)
dp[i] += 2
* ((dp[j] % mod)
* (dp[i - j - 2] % mod))
% mod;
}
// Ensure dp[i] stays within the modulo range
dp[i] %= mod;
}
}
// Return the number of ways to arrange num_people in a
// circle
return dp[n];
}
int main()
{
int n = 4;
int num_ways = numberOfWays(n);
if (num_ways == 0) {
cout << "Invalid number of people (number cannot "
"be negative)."
<< endl;
}
else {
cout << "The number of ways to arrange " << n
<< " people in a circle is " << num_ways
<< endl;
}
return 0;
}
import java.util.Arrays;
public class Main {
// Function to calculate the number of ways to arrange
// the people in a circle
public static long numberOfWays(int n)
{
// Handle invalid input (number of people cannot be
// negative)
if (n < 0) {
return 0;
}
final long mod
= 1_000_000_007L; // Modulo value to handle
// large numbers
// dp[i] stores the number of ways to arrange i
// people in a circle
long[] dp = new long[n + 1];
Arrays.fill(dp, 0);
// Base case: 0 people can be arranged in 1 way
// (empty circle)
dp[0] = 1;
// Loop through number of people (starting from 2,
// as 0 and 1 are handled)
for (int i = 2; i <= n; i += 2) {
// Loop through possible positions for the first
// person (from 0 to i-2)
for (int j = 0; j <= i - j - 2; j += 2) {
// If j is the last person (i-j-2), there's
// only one way to arrange the remaining
if (j == i - j - 2) {
dp[i] += (dp[j] * dp[i - j - 2]) % mod;
}
else {
// Otherwise, add the number of
// arrangements where the first j people
// form a group and the remaining i-j-2
// people form a group, multiplied by 2
// (since the arrangement can be
// clockwise or counter-clockwise)
dp[i] += 2
* ((dp[j] % mod)
* (dp[i - j - 2] % mod))
% mod;
}
// Ensure dp[i] stays within the modulo
// range
dp[i] %= mod;
}
}
// Return the number of ways to arrange num_people
// in a circle
return dp[n];
}
public static void main(String[] args)
{
int n = 4;
long num_ways = numberOfWays(n);
if (num_ways == 0) {
System.out.println(
"Invalid number of people (number cannot be negative).");
}
else {
System.out.println(
"The number of ways to arrange " + n
+ " people in a circle is " + num_ways);
}
}
}
def number_of_ways(n):
# Handle invalid input (number of people cannot be negative)
if n < 0:
return 0
mod = 1000000007 # Modulo value to handle large numbers
# dp[i] stores the number of ways to arrange i people in a circle
dp = [0] * (n + 1)
# Base case: 0 people can be arranged in 1 way (empty circle)
dp[0] = 1
# Loop through number of people (starting from 2, as 0 and 1 are handled)
for i in range(2, n + 1, 2):
# Loop through possible positions for the first person (from 0 to i-2)
for j in range(0, (i - 2) // 2 + 1, 2):
# If j is the last person (i-j-2), there's only one way to arrange the remaining
if j == i - j - 2:
dp[i] = (dp[i] + (dp[j] * dp[i - j - 2]) % mod) % mod
else:
# Otherwise, add the number of arrangements where the first j people form a group and
# the remaining i-j-2 people form a group, multiplied by 2 (since the arrangement
# can be clockwise or counter-clockwise)
dp[i] = (dp[i] + 2 * ((dp[j] % mod) *
(dp[i - j - 2] % mod)) % mod) % mod
# Return the number of ways to arrange num_people in a circle
return dp[n]
# Driver code
n = 4
num_ways = number_of_ways(n)
if num_ways == 0:
print("Invalid number of people (number cannot be negative).")
else:
print(
f"The number of ways to arrange {n} people in a circle is {num_ways}")
function numberOfWays(n) {
// Handle invalid input (number of people cannot be negative)
if (n < 0) {
return 0;
}
const mod = 1000000007; // Modulo value to handle large numbers
// dp[i] stores the number of ways to arrange i people in a circle
const dp = new Array(n + 1).fill(0);
// Base case: 0 people can be arranged in 1 way (empty circle)
dp[0] = 1;
// Loop through number of people (starting from 2, as 0 and 1 are handled)
for (let i = 2; i <= n; i += 2) {
// Loop through possible positions for the first person (from 0 to i-2)
for (let j = 0; j <= i - j - 2; j += 2) {
// If j is the last person (i-j-2), there's only one way to arrange the remaining
if (j === i - j - 2) {
dp[i] = (dp[i] + (dp[j] * dp[i - j - 2]) % mod) % mod;
} else {
// Otherwise, add the number of arrangements where the first j people form
// a group
// and the remaining i-j-2 people form a group, multiplied by 2
// (since the arrangement can be clockwise or counter-clockwise)
dp[i] = (dp[i] + 2 * ((dp[j] % mod) * (dp[i - j - 2] % mod)) % mod) % mod;
}
}
}
// Return the number of ways to arrange num_people in a circle
return dp[n];
}
// Driver code
const n = 4;
const numWays = numberOfWays(n);
if (numWays === 0) {
console.log("Invalid number of people (number cannot be negative).");
} else {
console.log(`The number of ways to arrange ${n} people in a circle is ${numWays}`);
}
Output
The number of ways to arrange 4 people in a circle is 2
Time Complexity: O(n^2) due to nested loops.
Auxiliary Space: O(n) due to dp vector.