Count All Valid Pickup and Delivery Options

Description

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

Solution(javascript)

/** backtracking or dp
 * @param {number} n
 * @return {number}
 */
// const countOrders = function (n) {
//   const picked = new Array(n).fill(false)
//   const delived = new Array(n).fill(false)
//   let result = 0
//   const aux = (current, currentP = [], currentD = []) => {
//     if (current >= 2 * n - 1) {
//       result += 1
//       return
//     }
//     for (let i = 0; i < currentP.length; i++) {
//       if (!currentP[i] && currentD[i]) {
//         return
//       }
//       if (!currentP[i]) {
//         currentP[i] = true
//         aux(current + 1, currentP, currentD)
//         currentP[i] = false
//       }
//       if (currentP[i] && !currentD[i]) {
//         currentD[i] = true
//         aux(current + 1, currentP, currentD)
//         currentD[i] = false
//       }
//     }
//   }
//   aux(0, picked, delived)
//   return result
// }


/** backtracking or dp ?
 * @param {number} n
 * @return {number}
 */
const countOrders1 = function (n) {
  let factorial = BigInt(1)
  let count = BigInt(1)
  const base = BigInt((10 ** 9) + 7)
  for (let i = 1; i <= n; i++) {
    factorial *= BigInt(i)
    count *= BigInt(2 * i - 1)
  }
  return Number((factorial * count) % base)
}

const countOrders = function (n) {
  let result = 1
  const base = (10 ** 9) + 7
  for (let i = 1; i <= n; i++) {
    result = (result * i * (2 * i - 1)) % base
  }
  return result % base
}