0ms 4-Lines O(n) Solution With Clear Explanation


  • 0
    O
    public class Solution {
            // if break 5 -> 2 * 3 > 5, you will never leave a 5 or larger number in the broken elements
            // if break 6 -> 3 * 3 > 6, you will never leave a 6 in the broken elements
            // also 3 * 3 > 2 * 2 * 2, so you break into as many 3 as possible
        public int integerBreak(int n) {
            int[] f = new int[Math.max(n + 1, 7)];
            f[2] = 1; f[3] = 2; f[4] = 4; f[5] = 6; f[6] = 9;
            for (int i = 7; i <= n; f[i] = 3 * f[i++ - 3]);
            return f[n];
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.