343. Integer Break

Greedy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int cuttingRope(int n) {
        // 2 = 1 + 1, product = 1 * 1 = 1
        // 3 = 1 + 2, product = 1 * 2 = 2
        // 4 = 2 + 2, product = 2 * 2 = 4

        if (n <= 3) {
            return n - 1;
        }

        // now n > 3
        int a = n / 3, b = n % 3;
        if (b == 0) {
            return (int) Math.pow(3, a);
        } else if (b == 1) {
            return (int) Math.pow(3, a - 1) * 4;
        } else {
            return (int) Math.pow(3, a) * 2;
        }
    }
}

Greedy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int cuttingRope(int n) {
        if (n <= 3) {
            return n - 1;
        }

        int p = 1000000007;
        long res = 1;

        while (n > 4) {
            res = res * 3 % p;
            n -= 3;
        }

        // now n: 2/3/4
        return (int) (res * n % p);
    }
}

References

343. Integer Break
剑指 Offer 14- I. 剪绳子
剑指 Offer 14- II. 剪绳子 II