We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Recursion
  4. K Factorization
  5. Discussions

K Factorization

  • vuhuutuan0
     + 0 comments

    My answer in Typescript, note includes.

    note: it is a litte confuse when Q ask me to print -1 but my code required to return [-1] insteads

    function kFactorization(n: number, A: number[]): number[] {
    /**
     * ya, every recursive function need a memorize
     */
    const memorize: { [n: number]: number[] } = {}

    /**
     * recursive function calculate reverseFactorization
     * 
     * + number [n] is number need to calculate
     * -> return [n*] that is smallest possible way to go, until 1
     */
    const reverseFactorization = (n: number): number[] => {
        // way end. return itseft
        if (n == 1) return [n]

        // already memorized, skip calculation
        if (n in memorize) return memorize[n]

        // calculate all possible way can go, only get the sortest way and "lexicographically"
        // memorized
        return memorize[n] = A.filter(a => n % a == 0)
            .map(b => [...reverseFactorization(n / b), n])
            .sort((a, b) => {
                // the sorter length
                if (a.length != b.length) return a.length - b.length
                // the top lexicographically
                else {
                    for (let i = 0; i < a.length; i++) {
                        if (a[i] < b[i]) return -1;
                        if (a[i] > b[i]) return 1;
                    }
                    return 0
                }
            }).shift() ?? []
    }

    // doing recursive reverseFactorization with stating is [n]
    let rs = reverseFactorization(n)

    // return
    if (rs.length == 0 || rs[0] != 1) return [-1]
    return rs
}