forked from shijbian/LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathinteger-break.py
More file actions
77 lines (70 loc) · 2.54 KB
/
integer-break.py
File metadata and controls
77 lines (70 loc) · 2.54 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
# Time: O(logn), pow is O(logn).
# Space: O(1)
# Given a positive integer n, break it into the sum of
# at least two positive integers and maximize the product
# of those integers. Return the maximum product you can get.
#
# For example, given n = 2, return 1 (2 = 1 + 1); given n = 10,
# return 36 (10 = 3 + 3 + 4).
#
# Note: you may assume that n is not less than 2.
#
# Hint:
#
# There is a simple O(n) solution to this problem.
# You may check the breaking results of n ranging from 7 to 10
# to discover the regularities.
class Solution(object):
def integerBreak(self, n):
"""
:type n: int
:rtype: int
"""
if n < 4:
return n - 1
# Proof.
# 1. Let n = a1 + a2 + ... + ak, product = a1 * a2 * ... * ak
# - For each ai >= 4, we can always maximize the product by:
# ai <= 2 * (ai - 2)
# - For each aj >= 5, we can always maximize the product by:
# aj <= 3 * (aj - 3)
#
# Conclusion 1:
# - For n >= 4, the max of the product must be in the form of
# 3^a * 2^b, s.t. 3a + 2b = n
#
# 2. To maximize the product = 3^a * 2^b s.t. 3a + 2b = n
# - For each b >= 3, we can always maximize the product by:
# 3^a * 2^b <= 3^(a+2) * 2^(b-3) s.t. 3(a+2) + 2(b-3) = n
#
# Conclusion 2:
# - For n >= 4, the max of the product must be in the form of
# 3^Q * 2^R, 0 <= R < 3 s.t. 3Q + 2R = n
# i.e.
# if n = 3Q + 0, the max of the product = 3^Q * 2^0
# if n = 3Q + 2, the max of the product = 3^Q * 2^1
# if n = 3Q + 2*2, the max of the product = 3^Q * 2^2
res = 0
if n % 3 == 0: # n = 3Q + 0, the max is 3^Q * 2^0
res = 3 ** (n // 3)
elif n % 3 == 2: # n = 3Q + 2, the max is 3^Q * 2^1
res = 3 ** (n // 3) * 2
else: # n = 3Q + 4, the max is 3^Q * 2^2
res = 3 ** (n // 3 - 1) * 4
return res
# Time: O(n)
# Space: O(1)
# DP solution.
class Solution2(object):
def integerBreak(self, n):
"""
:type n: int
:rtype: int
"""
if n < 4:
return n - 1
# integerBreak(n) = max(integerBreak(n - 2) * 2, integerBreak(n - 3) * 3)
res = [0, 1, 2, 3]
for i in xrange(4, n + 1):
res[i % 4] = max(res[(i - 2) % 4] * 2, res[(i - 3) % 4] * 3)
return res[n % 4]