Handshakes That Don't Cross

Updated on 02 June, 2025
Handshakes That Don't Cross header image

Problem Statement

In the given scenario, an even number of people, specified by numPeople, are standing around a circular table. Each person is to participate in exactly one handshake. The task is to determine the number of distinct ways these handshakes can occur without any two handshakes crossing each other. The representation of "crossing" implies that two handshakes should not involve people that interleave around the circle.

This computational problem becomes complex due to the potential large number of configurations, especially as the number of people increases. Given the potentially large output, the result should be returned modulo 10^9 + 7 to make the computation manageable and the numbers not overwhelmingly large.

Examples

Example 1

Input:

numPeople = 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)].

Example 2

Input:

numPeople = 6

Output:

5

Constraints

  • 2 <= numPeople <= 1000
  • numPeople is even.

Approach and Intuition

The problem's nature suggests a recursive or dynamic programming approach primarily because the solution seems to build on smaller subproblems. Specifically, the structure of the problem hints at the Catalan number sequence, which counts the number of ways to divide a set into pairs such that the pairs do not intersect or "cross" each other.

Here's a step-by-step breakdown based on the smaller examples:

  1. If one person is already shaking hands with another, they essentially divide the circle at their joining hands, creating two independent subproblems. Each of these smaller segments of the circle needs to compute the handshake arrangements without crossings, just like the original problem.
  2. The recursive formula can be defined like so: ( C(n) = \sum_{i=0}^{n-1} C(i) \times C(n-i-1) ) where ( C(n) ) refers to the number of ways ( n ) people can arrange the non-crossing handshakes (noting that ( n ) here would essentially be ( numPeople / 2 )).
  3. The base cases are:
    • ( C(0) = 1 ) — No person, one way to do nothing.
    • ( C(1) = 1 ) — Two persons, one way to shake hands.

With the above setup, a dynamic programming table can be populated. Each entry in the table will rely on previously computed values for smaller groups of people, reflecting the recursive nature of the problem. Each combination, as indexed by the recursive strategy, will contribute to the final count of arrangements for the full group of numPeople.

Thus, following the steps and computing based on past results enables the solution to be scalable up to the constraints provided. The use of modulo 10^9 + 7 ensures that even as numbers grow during computation, they remain manageable and fit within standard integer data limits of programming languages.

Solutions

  • C++
  • Java
  • Python
cpp
class HandshakeCombinations {
    const int MOD = 1'000'000'007;
    int modularMultiply(int x, int y) { return (long long)x * y % MOD; }

public:
    int calcWays(int people) {
        int pairs = people / 2;
        vector<int> inverse(pairs + 2);
        inverse[1] = 1;
        for (int i = 2; i <= pairs + 1; i++) {
            int div = MOD / i, rem = MOD % i;
            inverse[i] = MOD - modularMultiply(div, inverse[rem]);
        }
        int result = 1;
        for (int i = 0; i < pairs; i++) {
            result = modularMultiply(modularMultiply(2 * (2 * i + 1), inverse[i + 2]), result);
        }
        return result;
    }
};

The given C++ code provides a solution for calculating the number of ways people can perform handshakes without crossing. The solution tackles the problem by considering even numbers of people (pairwise handshakes) and utilizes modular arithmetic to handle large numbers, ensuring results fit within defined limits.

  • You calculate the number of non-crossing handshake ways based on the even number of people divided by two (those that can be paired). This is done in the calcWays method of the HandshakeCombinations class.
  • To handle modular arithmetic efficiently, there is a modularMultiply method that multiplies two numbers under a modulo defined as 1'000'000'007.
  • To invert modular values, an inverse vector is prepared. This vector uses properties of modular arithmetic to compute each number's modular inverse up to the count of pairs plus one. This step is crucial for further calculations.
  • Final result computation involves iterative modular multiplications using values from the inverse vector and intermediary results from previous iterations.

Edit the source code to experiment with different values by inputting different numbers of people in the calcWays method. Ensure to maintain integral multiples for the correct calculations of pair handshakes.

java
class Solution {
    private static int MOD = 1000000007;

    private int multiply(int x, int y) {
        return (int) ((long) x * y % MOD);
    }

    public int countWays(int totalPeople) {
        int half = totalPeople / 2;
        int[] inversion = new int[totalPeople / 2 + 2];
        inversion[1] = 1;
        for (int i = 2; i <= half + 1; i++) {
            int div = MOD / i, rem = MOD % i;
            inversion[i] = MOD - multiply(div, inversion[rem]);
        }
        int combinations = 1;
        for (int i = 0; i < half; i++) {
            combinations = multiply(multiply(2 * (2 * i + 1), inversion[i + 2]), combinations);
        }
        return combinations;
    }
}

The Java program provided calculates the number of ways to make handshakes such that no two handshakes cross each other, given an even number of total participants. The approach follows a mathematical strategy based on the combinatorial number theory related to Catalan numbers. Here’s a brief description of how the solution works:

  • Initialize a constant MOD to prevent overflow by taking results modulo (10^9 + 7).
  • Implement a helper function multiply(x, y) to compute the product of two numbers under modulo operations safely.
  • countWays(int totalPeople) is the main function which takes totalPeople (even) as input and determines the number of non-crossing handshake configurations:
    • Compute half as half the number of totalPeople because each unique non-crossing handshake pattern can be represented as a problem of pairing half pairs of participants.
    • Use an array inversion to store modular multiplicative inverses computed using a formula derived from properties of modular arithmetic.
    • Initialize the combinations to calculate the number of unique ways.
    • Loop through potential handshake positions and use the precomputed inverses, applying the multiplication helper method to consider all pairs and update combinations accordingly.
    • Finally, the function returns the total number of non-crossing handshake combinations computed.

This solution efficiently calculates the result by leveraging the properties of Catalan numbers and modular arithmetic, making it suitable for problems involving a large number of participants due to its optimized approach with precomputation and modular operations.

python
class Solution:
    def countHandshakes(self, people: int) -> int:
        mod = 1000000007
        pairs = people // 2
        inverse = [None] * (pairs+2)
        inverse[1] = 1
        for j in range(2, pairs+2):
            quotient = mod // j
            remainder = mod % j
            inverse[j] = mod - quotient * inverse[remainder] % mod
        catalan = 1
        for k in range(pairs):
            catalan = 2 * (2 * k + 1) * inverse[k + 2] * catalan % mod
        return catalan

This Python solution implements an algorithm to solve the "Handshakes That Don't Cross" problem. The problem is essentially about counting the number of ways to pair people such that no two handshakes cross each other, under the condition that people is even.

  • The algorithm leverages modular arithmetic with a modulus of 1000000007 to ensure the result fits within typical integer limits and avoid overflow.
  • The key mathematical concept used here is the Catalan number, which is pivotal in combinatorial problems involving properly nested and non-crossing structures.
  • An array called inverse is set up to store modular inverses using the extended Euclidean algorithm. The inverse is calculated through a dynamic programming approach to prevent recalculations and improve efficiency.
  • The solution iteratively computes the required Catalan number using a special product formula that involves the values from the inverse array.
  • Finally, it returns the computed Catalan number, which is the answer to the problem, representing the number of valid non-crossing handshake pairings.

Assure the people input is even, and if not, the function will not function correctly as it strictly depends on pair-based calculations. Adjust the code to handle odd inputs by returning 0 or a similar error handling, as non-paired people cannot form a valid set of non-crossing handshakes.

Comments

No comments yet.