343. Integer Break - LeetCode

'''
f(k) = (n/k)^k
-> ln(f(k)) = k ln(n/k)
-> d ln(f(k)) / d k = ln(n/k) + k(-1/k)
-> d f(k) / f(k) d k = ln(n/k) - 1
-> f′(k) = f(k) (ln(n/k) - 1)
find the maximum:
f′(k) = 0
-> ln(n/k) = 1
-> n/k = e, 2 or 3
'''


import math


class Solution1:  # O(n)
    # https://leetcode.com/problems/integer-break/solutions/4136961/easy-olog-n-time-with-o1-space-complexity-easy-math-solution-with-proofs/
    def integerBreak(self, n: int) -> int:
        if n < 4:
            return n - 1
        result = 1
        while n > 4:
            result *= 3
            n -= 3
        return n * result


class Solution2:  # O(log(n))
    def integerBreak(self, n: int) -> int:
        if n < 4:
            return n - 1
        return 2 ** (-n % 3) * 3 ** ((n - 4) // 3 + (n - 1) % 3)


class Solution:  # O(1)
    def integerBreak(self, n: int) -> int:
        if n < 4:
            return n - 1
        return int(math.pow(2, -n % 3) * math.pow(3, (n - 4) // 3 + (n - 1) % 3))