Skip to content

343. Integer Break

Description

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.

Return the maximum product you can get.

 

Example 1:

Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

 

Constraints:

  • 2 <= n <= 58

Solutions

Solution 1: Dynamic Programming

Thinking

Split \(n\) into at least two positives maximizing the product. Listing partitions is large. If the last part is \(j\), the rest is either kept whole or already optimal.

\(f[i]=\max_j \max(f[i-j]\cdot j,\,(i-j)\cdot j)\) with \(f[1]=1\). Fill by increasing \(i\); the answer is \(f[n]\). \(n\le 58\) allows \(O(n^2)\).

We define \(f[i]\) as the maximum product that can be obtained by splitting the positive integer \(i\), with an initial condition of \(f[1] = 1\). The answer is \(f[n]\).

Consider the last number \(j\) split from \(i\), where \(j \in [1, i)\). For the number \(j\) split from \(i\), there are two cases:

  1. Split \(i\) into the sum of \(i - j\) and \(j\), without further splitting, where the product is \((i - j) \times j\);
  2. Split \(i\) into the sum of \(i - j\) and \(j\), and continue splitting, where the product is \(f[i - j] \times j\).

Therefore, we can derive the state transition equation:

\[ f[i] = \max(f[i], f[i - j] \times j, (i - j) \times j) \quad (j \in [0, i)) \]

Finally, returning \(f[n]\) will suffice.

The time complexity is \(O(n^2)\), and the space complexity is \(O(n)\). Here, \(n\) is the given positive integer.

1
2
3
4
5
6
7
class Solution:
    def integerBreak(self, n: int) -> int:
        f = [1] * (n + 1)
        for i in range(2, n + 1):
            for j in range(1, i):
                f[i] = max(f[i], f[i - j] * j, (i - j) * j)
        return f[n]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public int integerBreak(int n) {
        int[] f = new int[n + 1];
        f[1] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j < i; ++j) {
                f[i] = Math.max(Math.max(f[i], f[i - j] * j), (i - j) * j);
            }
        }
        return f[n];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int integerBreak(int n) {
        vector<int> f(n + 1);
        f[1] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j < i; ++j) {
                f[i] = max({f[i], f[i - j] * j, (i - j) * j});
            }
        }
        return f[n];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func integerBreak(n int) int {
    f := make([]int, n+1)
    f[1] = 1
    for i := 2; i <= n; i++ {
        for j := 1; j < i; j++ {
            f[i] = max(max(f[i], f[i-j]*j), (i-j)*j)
        }
    }
    return f[n]
}

1
2
3
4
5
6
7
8
9
function integerBreak(n: number): number {
    const f = Array(n + 1).fill(1);
    for (let i = 3; i <= n; i++) {
        for (let j = 1; j < i; j++) {
            f[i] = Math.max(f[i], j * (i - j), j * f[i - j]);
        }
    }
    return f[n];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
impl Solution {
    pub fn integer_break(n: i32) -> i32 {
        let n = n as usize;
        let mut f = vec![0; n + 1];
        f[1] = 1;
        for i in 2..=n {
            for j in 1..i {
                f[i] = f[i].max(f[i - j] * j).max((i - j) * j);
            }
        }
        f[n] as i32
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
/**
 * @param {number} n
 * @return {number}
 */
var integerBreak = function (n) {
    const f = Array(n + 1).fill(1);
    for (let i = 2; i <= n; ++i) {
        for (let j = 1; j < i; ++j) {
            f[i] = Math.max(f[i], f[i - j] * j, (i - j) * j);
        }
    }
    return f[n];
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
public class Solution {
    public int IntegerBreak(int n) {
        int[] f = new int[n + 1];
        f[1] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j < i; ++j) {
                f[i] = Math.Max(Math.Max(f[i], f[i - j] * j), (i - j) * j);
            }
        }
        return f[n];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
#define max(a, b) (((a) > (b)) ? (a) : (b))

int integerBreak(int n) {
    int* f = (int*) malloc((n + 1) * sizeof(int));
    f[1] = 1;
    for (int i = 2; i <= n; ++i) {
        f[i] = 0;
        for (int j = 1; j < i; ++j) {
            f[i] = max(f[i], max(f[i - j] * j, (i - j) * j));
        }
    }
    return f[n];
}

Solution 1: Mathematics

Thinking

Method 1 does not name the optimal parts. For \(n\ge 4\) use as many \(3\)s as possible; a remainder \(1\) becomes \(2+2\), a remainder \(2\) keeps an extra \(2\). For \(n<4\) the product is \(n-1\). Closed form in \(O(1)\).

When \(n < 4\), since the problem requires splitting into at least two integers, \(n - 1\) yields the maximum product. When \(n \geq 4\), we split into as many \(3\)s as possible. If the last segment remaining is \(4\), we split it into \(2 + 2\) for the maximum product.

The time complexity is \(O(1)\), and the space complexity is \(O(1)\).

1
2
3
4
5
6
7
8
9
class Solution:
    def integerBreak(self, n: int) -> int:
        if n < 4:
            return n - 1
        if n % 3 == 0:
            return pow(3, n // 3)
        if n % 3 == 1:
            return pow(3, n // 3 - 1) * 4
        return pow(3, n // 3) * 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int integerBreak(int n) {
        if (n < 4) {
            return n - 1;
        }
        if (n % 3 == 0) {
            return (int) Math.pow(3, n / 3);
        }
        if (n % 3 == 1) {
            return (int) Math.pow(3, n / 3 - 1) * 4;
        }
        return (int) Math.pow(3, n / 3) * 2;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int integerBreak(int n) {
        if (n < 4) {
            return n - 1;
        }
        if (n % 3 == 0) {
            return pow(3, n / 3);
        }
        if (n % 3 == 1) {
            return pow(3, n / 3 - 1) * 4;
        }
        return pow(3, n / 3) * 2;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func integerBreak(n int) int {
    if n < 4 {
        return n - 1
    }
    if n%3 == 0 {
        return int(math.Pow(3, float64(n/3)))
    }
    if n%3 == 1 {
        return int(math.Pow(3, float64(n/3-1))) * 4
    }
    return int(math.Pow(3, float64(n/3))) * 2
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function integerBreak(n: number): number {
    if (n < 4) {
        return n - 1;
    }
    const m = Math.floor(n / 3);
    if (n % 3 == 0) {
        return 3 ** m;
    }
    if (n % 3 == 1) {
        return 3 ** (m - 1) * 4;
    }
    return 3 ** m * 2;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
impl Solution {
    pub fn integer_break(n: i32) -> i32 {
        if n < 4 {
            return n - 1;
        }
        match n % 3 {
            0 => return (3 as i32).pow((n / 3) as u32),
            1 => return (3 as i32).pow((n / 3 - 1) as u32) * 4,
            _ => return (3 as i32).pow((n / 3) as u32) * 2,
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
/**
 * @param {number} n
 * @return {number}
 */
var integerBreak = function (n) {
    if (n < 4) {
        return n - 1;
    }
    const m = Math.floor(n / 3);
    if (n % 3 == 0) {
        return 3 ** m;
    }
    if (n % 3 == 1) {
        return 3 ** (m - 1) * 4;
    }
    return 3 ** m * 2;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
public class Solution {
    public int IntegerBreak(int n) {
        if (n < 4) {
            return n - 1;
        }
        if (n % 3 == 0) {
            return (int)Math.Pow(3, n / 3);
        }
        if (n % 3 == 1) {
            return (int)Math.Pow(3, n / 3 - 1) * 4;
        }
        return (int)Math.Pow(3, n / 3) * 2;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int integerBreak(int n) {
    if (n < 4) {
        return n - 1;
    }
    if (n % 3 == 0) {
        return (int) pow(3, n / 3);
    }
    if (n % 3 == 1) {
        return (int) pow(3, n / 3 - 1) * 4;
    }
    return (int) pow(3, n / 3) * 2;
}

Comments