O(logn) Ruby solution- 69ms


  • 0
    T

    Solution uses DP and recursion.

    # @param {Integer} n
    # @return {Integer}
    
    @min_to_num = {0 => 0}
    
    @squares = []
    
    def get_all_perfect_squares(n)
        i = 1
        while (i * i <= n)
            @squares << (i * i)
            @min_to_num[i * i] = 1
            i += 1
        end
    end
    
    def min_num_squares(n)
    
        if (@min_to_num.key?(n))
            return @min_to_num[n]
        end
        
        mins = []
        
        for square in @squares do
            if (square > n)
                break
            else 
                mins << (n / square) + min_num_squares(n % square)
            end
        end
        
        @min_to_num[n] = mins.min
        return @min_to_num[n]
    end
    
    def num_squares(n)
        @squares = []
        get_all_perfect_squares(n)
        
        return min_num_squares(n)
    end
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.