#1359
Hard Algorithms Count all valid pickup and delivery options
Math Dynamic Programming Combinatorics
64.9% acceptance
Feb 25, 2026
3089
233
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.
Solution
Rust
Time O(n)
Space O(1)
impl Solution {
pub fn count_orders(n: i32) -> i32 {
const MOD: i64 = 1_000_000_007;
let mut ans: i64 = 1;
for i in 2..=n as i64 {
// positions available = 2*i - 1 slots for pickup, then (2*i-1) positions for delivery
ans = ans * (2 * i - 1) % MOD * i % MOD;
}
ans as i32
}
}