Java double O(1) time/space 0ms solution (Thought By Thought, Math, Ultra Understandable)
Thoughts Before Coding\nOften when approached with patten based problems, I find it helpful to run through some examples. I have hand computed the answer for th
## Thoughts Before Coding\nOften when approached with patten based problems, I find it helpful to run through some examples. I have hand computed the answer for the first 11 numbers by hand. You do not need to do 11, but I wanted to show an abudance of numbers to spot a pattern in.\n```\n          n = 2 : 1*1\n          n = 3 : 2*1\n          n = 4 : 2*2\n          n = 5 : 3*2\n          n = 6 : 3*3\n          n = 7 : 3*2*2\n          n = 8 : 3*3*2\n          n = 9 : 3*3*3\n          n = 10: 3*3*2*2\n          n = 11: 3*3*3*2\n```\nYou may notice something about this pattern- it is mostly 2\'s and 3\'s. Why is this? Another post here goes into calculus, but I think that makes it needlessly difficult. Instead approach it with the following observation:\n***The more addeds (i.e. pieces) > 1 that the number is decomposed to, the larger the product.***\n\nWhy is this? It should be clear that addends of 0 or 1 are "bad" as multiplying by 0 turns the product to 0, and multipling any integer by 1 does not change the value of the integer. So if one were to use all 2\'s, there is a problem: not every number can be summed with only 2\'s. For odd numbers, adding on a remaining 1 does not change the product, but turning a two into a three and using fewer twos will change the product. \nFor example:\n```\n2+2+2+1 = 7\n2*2*2*1 = 8\n-----\n2+2+3 = 7\n2*2*3 = 12\n-----\n12 > 7\n```\nThis pattern will always hold. The reasoning behind that is if you multiply by 4 instead of 3 or 2, 4 = 2\\*2 so there really is no difference. If you multiply by 5, you get a scale factor of 5 whereas multipling by 2\\*3 (because 2+3 = 5) gives a scale factor of 6. You can show that for any number, its always better to break it into the most pieces > 1. This gives the math an exponent-like effect as opposed to multiplication.\n\n# Turning This Into Code\nPersonally, I have found DP to not be very intuitive for this problem. As it is not the optimal solution, I will leave that approach to other discussion posts. Instead, we can use our math observations above to create a clean, readable solution that relies on math to perform in constant time.\n\nFrom our math pattern, there are a few more things to notice.\n```\n          n = 2 : 1*1\n          n = 3 : 2*1\n          n = 4 : 2*2\n          n = 5 : 3*2\n          n = 6 : 3*3\n          n = 7 : 3*2*2\n          n = 8 : 3*3*2\n          n = 9 : 3*3*3\n          n = 10: 3*3*2*2\n          n = 11: 3*3*3*2\n```\n\nThere is no number 3 for the n = 2, n = 3 and n = 4. These are our edge cases. Otherwise, there is a clear pattern that emerges. In plain English, our algorithm would be\n\n* For the input number n, if only threes can be used without remainder, return the product of the amount of threes that make it up.\n* Otherwise, if there is a remainder of 1 when subtracting threes, use one less three than you can fit, and multiply by 2 and then 2 again (because 3\\*1 < 2\\*2). Return this product.\n*  Lastly if there is a remainder of 2 when subtracting threes, use as many threes as possible, and then finally a 2. Return this product.\n\nThis behavior with finding how many of a number fit, and the remainder is what characterizes the modulo operation. This brings us to...\n## The Code\n```\nclass Solution {\n    private static final int[] bases = {0,0,1,2,4};\n    public int integerBreak(int n) {\n        if(n <= 4)\n          return bases[n];\n        else\n          switch(n%3){\n            case 0 :\n              return (int) Math.pow(3,n/3);\n            case 1 :\n              return (int) Math.pow(3,n/3 - 1)*2*2;\n            default: // case 2\n              return (int) Math.pow(3,n/3)*2;\n          }\n    }\n}\n```\n## Time and Space Analysis\nThe only additional memory used is constant, the static array for edge cases. The only time complexity hiccup is the pow function. The Math.pow function is not iterative- see [this stack overflow thread](https://stackoverflow.com/questions/32418731/java-math-powa-b-time-complexity) for implementation details on how this is.\n\nAs a result, the above code runs in constant time and constant space, beating 100% of Java submissions.\n\nIf you liked this write-up or have any questions, please leave a comment or upvote for visibility. Also checkout some of my other more detailed writeups from this account. Thank you -AC
['Math', 'Java']