Stone Division, Revisited

  • + 0 comments

    My answer in Typescript

    function stoneDivision(n: number, s: number[]): number {
        /**
         * Build a recursion function that have
         * 
         * + number [n] is size of a pile
         * + number [s] is set of divider
         * -> return 0 if [n] can't be divided by any of [s]
         *  * recursion mean this couple can't be go furthur
         * -> return 1 if [n] can divided
         *  * number [d] is a number in [s] that fit conditions
         *  * number [n] can be divided multiple times, so multiply by [n]/[d]
         *  * recursion mean this couple is nice, plus
         */
    
        const memo: { [key: string]: number } = {}
        const recurse = (n: number): number => {
            if (n in memo) return memo[n]
    
            let max = 0
            for (let d of s) {
                if (d != n && n % d == 0) {
                    max = Math.max(max, 1 + (n / d) * recurse(d))
                }
            }
    
            return memo[n] = max
        }
    
        return recurse(n)
    }