Skip to main content

343. Integer Break - LeetCode

· One min read
'''
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))