Problem

Given n orders, each order consists of a pickup and a delivery service.

Count all valid pickup/delivery possible sequences such that delivery(i) is always after of pickup(i). 

Since the answer may be too large, return it modulo 10^9 + 7.

Examples

Example 1

1
2
3

Input: n = 1
Output: 1
Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.

Example 2

1
2
3
4
5

Input: n = 2
Output: 6
Explanation: All possible orders: 
(P1,P2,D1,D2), (P1,P2,D2,D1), (P1,D1,P2,D2), (P2,P1,D1,D2), (P2,P1,D2,D1) and (P2,D2,P1,D1).
This is an invalid order (P1,D2,P2,D1) because Pickup 2 is after of Delivery 2.

Example 3

1
2

Input: n = 3
Output: 90

Solution

Method 1 – Combinatorial Counting with Factorials

Intuition

For each order, the pickup must occur before its delivery. For n orders, there are 2n events (n pickups and n deliveries). The total number of ways to arrange these events such that each delivery comes after its pickup is the product of the number of ways to insert each delivery after its pickup. This leads to the formula: ans = 1 * 3 * 5 * ... * (2n - 1) * n! Or, more generally, ans = (2n)! / (2^n * n!).

Approach

  1. Initialize ans as 1.
  2. For each order i from 1 to n:
  • There are 2*i - 1 possible positions to insert the delivery for the ith order.
  • Multiply ans by i (for pickup) and by (2*i - 1) (for delivery).
  • Take modulo 10^9 + 7 at each step to avoid overflow.
  1. Return ans.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
   int countOrders(int n) {
      long ans = 1, mod = 1e9 + 7;
      for (int i = 1; i <= n; ++i) {
        ans = ans * i % mod;
        ans = ans * (2 * i - 1) % mod;
      }
      return (int)ans;
   }
};
1
2
3
4
5
6
7
8

func countOrders(n int) int {
   ans, mod := 1, int(1e9+7)
   for i := 1; i <= n; i++ {
      ans = ans * i % mod
      ans = ans * (2*i-1) % mod
   }
   return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
   public int countOrders(int n) {
      long ans = 1, mod = (long)1e9 + 7;
      for (int i = 1; i <= n; i++) {
        ans = ans * i % mod;
        ans = ans * (2 * i - 1) % mod;
      }
      return (int)ans;
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
   fun countOrders(n: Int): Int {
      var ans = 1L
      val mod = 1_000_000_007L
      for (i in 1..n) {
        ans = ans * i % mod
        ans = ans * (2 * i - 1) % mod
      }
      return ans.toInt()
   }
}
1
2
3
4
5
6
7
8

class Solution:
   def countOrders(self, n: int) -> int:
      ans: int = 1
      mod: int = 10**9 + 7
      for i in range(1, n + 1):
        ans = ans * i % mod
        ans = ans * (2 * i - 1) % mod
      return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
   pub fn count_orders(n: i32) -> i32 {
      let mut ans: i64 = 1;
      let m: i64 = 1_000_000_007;
      for i in 1..=n as i64 {
        ans = ans * i % m;
        ans = ans * (2 * i - 1) % m;
      }
      ans as i32
   }
}
1
2

- ⏰ Time complexity: `O(n)`
- 🧺 Space complexity: `O(1)`