1359. Count All Valid Pickup and Delivery Options

Problem

Tags: Math, Dynamic Programming, Combinatorics

Given n orders, each order consist in pickup and delivery services.

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.

Example 1:

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

Example 2:

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:

Input: n = 3
Output: 90

Constraints:

• 1 <= n <= 500

Code

C

// 1359. Count All Valid Pickup and Delivery Options (1/26/54148)
// Runtime: 0 ms (86.67%) Memory: 5.63 MB (6.67%) 

int countOrders (int n) {
    int64_t ans = 1, fact = 1;
    int64_t mod = 1000000007;
    
    for (int i = 1; i <= n; i++) {
        fact *= i;
        fact %= mod;
    }
    
    for (int i = 1; i <= n; i++) {
        ans *= 2 * i - 1;
        ans %= mod;
    }
    
    return (ans * fact) % mod;
}

CPP

// 1359. Count All Valid Pickup and Delivery Options (2/8/54148)
// Runtime: 0 ms (94.84%) Memory: 5.84 MB (73.87%) 

class Solution {
public:
    int countOrders(int n) {
        int64_t ans = 1;
        int64_t mod = 1000000007;
        
        for (int i = 2; i <= n; i++) {
            ans *= 2 * i - 1;
            ans %= mod;
        }
        
        for (int i = 2; i <= n; i++) {
            ans *= i;
            ans %= mod;
        }
        
        return ans;
    }
};

CS

// 1359. Count All Valid Pickup and Delivery Options (2/11/54148)
// Runtime: 31 ms (81.08%) Memory: 25.25 MB (67.57%) 

public class Solution {
    public int CountOrders(int n) {
        long ans = 1;
        long mod = 1000000007;
        
        for (int i = 2; i <= n; i++) {
            ans *= 2 * i - 1;
            ans %= mod;
        }
        
        for (int i = 2; i <= n; i++) {
            ans *= i;
            ans %= mod;
        }
        
        return (int)ans;
    }
}

JAVA

// 1359. Count All Valid Pickup and Delivery Options (2/9/54148)
// Runtime: 0 ms (94.99%) Memory: 41.28 MB (35.76%) 

class Solution {
    public int countOrders(int n) {
        long ans = 1;
        long mod = 1000000007;
        
        for (int i = 2; i <= n; i++) {
            ans *= 2 * i - 1;
            ans %= mod;
        }
        
        for (int i = 2; i <= n; i++) {
            ans *= i;
            ans %= mod;
        }
        
        return (int)ans;
    }
}

JS

// 1359. Count All Valid Pickup and Delivery Options (1/31/54148)
// Runtime: 59 ms (84.00%) Memory: 42.36 MB (48.00%) 

/**
 * @param {number} n
 * @return {number}
 */
function countOrders(n) {
    let ans = 1;
    const mod = 1000000007;
    
    for (let i = 1; i <= n; i++) {
        ans *= 2 * i - 1;
        ans %= mod;
    }
    
    for (let i = 1; i <= n; i++) {
        ans *= i;
        ans %= mod;
    }
    
    return ans;
};

PY

# 1359. Count All Valid Pickup and Delivery Options (2/10/54148)
# Runtime: 24 ms (50.00%) Memory: 13.43 MB (55.88%) 

class Solution(object):
    def countOrders(self, n):
        """
        :type n: int
        :rtype: int
        """
        ans = 1
        mod = 1000000007
        
        for i in range(2, n+1):
            ans *= 2 * i - 1
            ans %= mod
        
        for i in range(2, n+1):
            ans *= i
            ans %= mod
        
        return ans

PY3

# 1359. Count All Valid Pickup and Delivery Options (2/10/54148)
# Runtime: 42 ms (58.80%) Memory: 13.78 MB (91.90%) 

class Solution:
    def countOrders(self, n: int) -> int:
        ans = 1
        mod = 1000000007
        
        for i in range(2, n+1):
            ans *= 2 * i - 1
            ans %= mod
        
        for i in range(2, n+1):
            ans *= i
            ans %= mod
        
        return ans

RB

# 1359. Count All Valid Pickup and Delivery Options (2/17/54148)
# Runtime: 48 ms (0.00%) Memory: 210.95 MB (0.00%) 

# @param {Integer} n
# @return {Integer}
def count_orders(n)
    ans = 1
    mod = 1000000007
    
    for i in 2..n
        ans *= i
        ans %= mod
    end
    
    for i in 2..n
        ans *= i * 2 - 1
        ans %= mod
    end
    
    return ans
end

RS

// 1359. Count All Valid Pickup and Delivery Options (2/7/54148)
// Runtime: 1 ms (0.00%) Memory: 2.06 MB (0.00%) 

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

        for i in 1i64..=(n as i64) {
            ans *= i;
            ans %= modulo;
        }

        return ans as i32;
    }
}

TS

// 1359. Count All Valid Pickup and Delivery Options (1/31/54148)
// Runtime: 60 ms (0.00%) Memory: 44.80 MB (0.00%) 

function countOrders(n: number): number {
    let ans = 1;
    const mod = 1000000007;
    
    for (let i = 1; i <= n; i++) {
        ans *= 2 * i - 1;
        ans %= mod;
    }
    
    for (let i = 1; i <= n; i++) {
        ans *= i;
        ans %= mod;
    }
    
    return ans;
};