Ropes

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
4 upvotes
Asked in companies
UberUnthinkable Solutions

Problem statement

You are given an integer 'N'. There are 'N' children standing in a circle. They are given 'N' / 2 ropes. They have to choose pairs in such a way that one child holds one end of the rope and the other child holds the other end. Your task is to determine the total number of different possible arrangements such that:

Note:

1. In each arrangement, there is exactly one child at either end of the rope. This means one rope will be held by exactly two children.
2. No rope should cross any other rope.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the 'T' test cases follow. 

The first line of each test case contains a single integer, 'N'.
Output Format: 
For each test case, print a single integer, denoting the total number of required arrangements. Since, the answer may be very large, print the answer modulo 10 ^ 9 + 7.

Output for each test case will be printed in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N < 2 * 10^3
N is always even.

Where ‘T’ denotes the number of test cases and 'N' represents the total number of children.

Time Limit: 1sec
Sample Input 1:
1
2
Sample Output 1:
1
Explanation for Sample Input 1:

example

There is only one way to arrange children in pairs. It is shown in the above diagram.
Sample Input 2:
1
4
Sample Output 2:
2
Explanation for sample input 2:

example example example

There are just two ways to arrange for children which hold the given conditions. In the first two ways, ropes are not crossing each other. We can see in the third diagram that the ropes are crossing each other, hence we can not consider this way, and thus our answer is 2.
Hint

For a pair of children, find the possible arrangements to the left and right of it.

Approaches (3)
Using Recursion

Approach: The approach is to break down the problem into some smaller subproblems. We can observe the fact that if a pair of children is chosen and handed a rope, then all the children to the left of this rope must be able to form pairs, and similarly on the right side. 

If the number of children on the left side is ‘X’, then the number of children on the right side will be ‘N - X - 2’. So, our problem breaks down into finding the ways for ‘X’ and for ‘N-2-X’ and multiplying them.

 Note that ‘X’ can have multiple values and we need to find all possible arrangements so we need to sum up the number of ways for each value of ‘X’. 

 

Algorithm is as follows:

  1. If 'N' = 0, return 1. This is because if there are no children, then there is only one way to arrange this, and that is to give no one any rope.
  2. Now, define 'MOD' = 10^9 + 7.
  3. Define a variable, say totalArrangements, to store the total number of ways to form pairs.
  4. Now, run a loop from ‘LEFT’ = 0 to ‘LEFT’ < N, with an increment of 2, after every loop because we are considering only even numbers, and do:
    1. The number of children on the right side will be ‘N’ - ‘LEFT’ - 2. Store this value in a variable, say ‘RIGHT’.
    2. Now, add the product, findTotalArrangements(left) * findTotalArrangements(right) to our variable, ‘SUM’. This is because if there are ‘LEFT’ children on the left side, then they can be arranged in findTotalArrangements(left) ways. Similarly, if there are ‘RIGHT’ children, then they can be arranged in findTotalArrangements(right) ways. So, total possible arrangements will be the product of these values.
    3. Now, take the modulo of ‘TOTALARRAGEMENT’ to avoid any overflow.
  5. Finally, return this value of ‘TOTALARRAGEMENT’.
Time Complexity

O(2 ^ N), where ‘N’ is the total number of children.

 

For every N, we are recursively solving the problem for smaller subproblems until we reach 0. 

The smaller subproblems will again solve for even smaller subproblems. This has a complexity of O(2^N).

Space Complexity

O(N), where ‘N’ is the total number of children.

 

We are recursively calling the functions and using a recursion stack of at max size ‘N’.

Code Solution
(100% EXP penalty)
Ropes
Full screen
Console