Count All Valid Pickup and Delivery Options

How it works

The total number of arrangements of 2n events is (2n)!. However, for each order, the delivery must come after the pickup, which has a 1/2 probability in a random arrangement. Since we have n independent orders, the valid arrangements are (2n)! / 2^n.

Steps

1. Initialize the result to 1.
2. Iterate through slots from 1 to 2n.
3. Multiply the result by the current slot number.
4. Whenever the slot is even (meaning we just placed a delivery), divide by 2 to account for the ordering constraint.
5. Take modulo at each step and return the final result.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Forgetting Modular Arithmetic

The result grows extremely fast (factorial-like), causing integer overflow. You must take modulo at each multiplication step, not just at the end.

Allowing Delivery Before Pickup

Some solutions incorrectly count all permutations of 2n events. The constraint that each delivery must come after its pickup is essential and reduces valid arrangements by a factor of 2^n.

Integer Overflow in Intermediate Calculations

When multiplying two integers before taking modulo, the intermediate result can overflow. Use explicit casting to long or 64-bit integers.

Miscounting Slot Choices

In the combinatorics approach, the valid choices for placing a pickup-delivery pair is slots * (slots - 1) / 2, not slots * (slots - 1). The division by 2 accounts for the fact that pickup must come before delivery.

Wrong Base Case in Recursion

The base case should return 1 when all orders are picked AND delivered, not just when all are picked. Returning early causes undercounting.

class Solution:
    def countOrders(self, n: int) -> int:
        MOD = 1000000007
        res = 1

        for slot in range(1, 2 * n + 1):
            res  *= slot
            if slot % 2 == 0:
                res >>= 1
            res %= MOD

        return res

class Solution {
public:
    int countOrders(int n) {
        const int MOD = 1000000007;
        long long res = 1;

        for (int slot = 1; slot <= 2 * n; slot++) {
            res *= slot;
            if (slot % 2 == 0) {
                res >>= 1;
            }
            res %= MOD;
        }
        return (int) res;
    }
};