const cache = new Map(); const factorial = (n) => { let sum = 1n; console.log(`n:${n}, sum:${sum}`) console.log("cache") console.log(cache) if (cache.has(n)) return cache.get(n); let tmpN = n; while (n > 0n) { sum *= n; n--; } cache.set(tmpN, sum); return sum; return factorial(n - 1n, sum * n); } // combination const getCombination = (n, r) => { console.log(`n:${n}, r:${r}`) // C(n + r - 1, r) // let n = total + r - 1; // let n1 = // C(n, r) = n! / (r! * (n - r)!) // // nPr - n!/(n - r)! // console.log(`${factorial(n)} / ${factorial(n - r)}`) // return factorial(n) / factorial(n - r); n = BigInt(n), r = BigInt(r); let x = factorial(n) / (factorial(r) * factorial(n - r)); console.log(`${factorial(n)} / (${factorial(r)} * ${factorial(n - r)}) -> ${x}`) console.log(x) return x; return factorial(n) / (factorial(r) * factorial(n - r)); } /** * @param {number[]} nums * @return {number} */ const numOfWays = (nums) => { console.log(nums) // let totalPossible = 1; const findPossibleWays = (numsList) => { console.log("numsList"); console.log(numsList); if (numsList.length <= 2) return 1n; let root = numsList.shift(), leftList = [], rightList = [], leftCount = 0, rightCount = 0, total = 0; console.log("_________________ root:" + root) while (numsList.length > 0) { total++; let curr = numsList.shift(); if (curr < root) { leftList.push(curr); } else { rightList.push(curr); } } leftCount = leftList.length, rightCount = rightList.length; // console.log("total") // console.log(total) console.log(`-> ${total}C${leftCount}`) // nCr // console.log((leftSum * rightSum) % ((10 ^ 9) + 7)) // totalPossible *= (leftSum * rightSum) - 1; // let a = findPossibleWays(leftList), b = findPossibleWays(rightList), c = getCombination(total, leftCount); // console.log(a) // console.log(b) // console.log(c) // // console.log(`${a} * ${b} * ${c} = ${a * b * c}`) // return a * b * c; return findPossibleWays(leftList) * findPossibleWays(rightList) * getCombination(total, leftCount); } // console.log("findPossibleWays(nums)") // console.log(findPossibleWays(nums)) // return (findPossibleWays(nums) - 1); let x = findPossibleWays(nums) - 1n; console.log(`x:${x}`) return (x) % BigInt(Math.pow(10, 9) + 7); return totalPossible; return totalPossible; return totalPossible % ((10 ^ 9) + 7); }; let x = null; // let x = numOfWays([1,2,3]); // 0 // let x = numOfWays([2,1,3]); // 1 // let x = numOfWays([3, 4, 5, 1, 2]); // 5 // let x = numOfWays([3, 1, 2, 5, 4, 6]); // 19 // x = numOfWays([9, 4, 2, 1, 3, 6, 5, 7, 8, 14, 11, 10, 12, 13, 16, 15, 17, 18]); // x = numOfWays([9, 4, 2, 1, 3, 6, 5, 7, 8, 14, 11, 10, 12, 13, 16, 15, 17, 18]); // 216212978 x = numOfWays([31, 23, 14, 24, 15, 12, 25, 28, 5, 35, 17, 6, 9, 11, 1, 27, 18, 20, 2, 3, 33, 10, 13, 4, 7, 36, 32, 29, 8, 30, 26, 19, 34, 22, 21, 16]); // 936157466 console.log("Result"); console.log(x);