Ruby Solution


  • 0

    Let's start with some concrete examples to find some patterns.

    n solution   product
    2  (1,1)     1
    3  (1,2)     2
    4  (2,2)     4
    ---------------------
    5  (3,     2) 6
    6  (3,     3) 9
    7  (3,     4) 12
    8  (3,3,   2) 18
    9  (3,3,   3) 27
    10 (3,3,   4) 36
    11 (3,3,3, 2) 54
    12 (3,3,3, 3) 81
    13 (3,3,3, 4) 108
    ...
    

    It seems like the optimal solution has three possible forms

    [1] 3,3, ... 3, 2
    [2] 3,3, ... 3, 3
    [3] 3,3, ... 3, 4
    

    Let's do some simple math.

    n = (3+3+....+3) + k 
    where k belongs to set {2,3,4}
    
    n-2 = (3+3+....+3) + (k-2)
    where (k-2) belongs to set {0,1,2}
    
    NOTE: In Ruby, integer division strip the decimal value (e.g. 1/2 equals 0)
    (n-2)/3 = num_of_3s_in_parenthesis + (k-2)/3
    (n-2)/3  = num_of_3s_in_parenthesis
    
    Thus
    k = n - num_of_3s_in_parenthesis*3
    

    def integer_break(n)
        if n == 2
            1
        elsif n == 3
            2
        else
            num_of_three = (n-2)/3
            3**num_of_three * (n-3*num_of_three)
        end
    end
    

Log in to reply
 

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