Python 8-lines simple O(1)
From the hint:\n\n> 7 = 3 + 4 = 12\n\n> 8 = 3 + 3 + 2 = 18 \n\n> 9 = 3 + 3 + 3 = 27\n\n> 10 = 3 + 3 + 4 = 36\n\n> 11 = 3 + 3 + 3 + 2 = 54\n\n> 12 = 3 + 3 + 3 + 
> From the hint:\n\n> 7 = 3 + 4 = 12\n\n> 8 = 3 + 3 + 2 = 18 \n\n> 9 = 3 + 3 + 3 = 27\n\n> 10 = 3 + 3 + 4 = 36\n\n> 11 = 3 + 3 + 3 + 2 = 54\n\n> 12 = 3 + 3 + 3 + 3 = 81\n\n*Three* is a *magic* number.\n\n\n\n    class Solution(object):\n        def integerBreak(self, n):\n            if n == 2 or n == 3:\n                return n - 1\n            if n % 3 == 0:\n                return 3**(n/3)\n            if n % 3 == 1:\n                return 3**(n/3 - 1)*4\n            if n % 3 == 2:\n                return 3**(n/3)*2
['Python']