# 343. Integer Break

## Tóm tắt đề
Cho số $n$. Phân tích số $n$ thành $k \ge 2$ số tự nhiên sao cho tích của chúng lớn nhất.

## Giới hạn
$2 \le n \le 58$

## Lời giải
Nếu $n < 4$ thì đáp án là $n - 1$, vì ta chỉ có thể tách $2$ thành $\{1, 1\}$, và $3$ thành $\{2, 1\}$.

Với $n \ge 4$, nếu ta có thể tách $n$ thành các số $i, j$ với $i, j \ge 2$ thì luôn có $i \times j \ge n$, vì $i \times j \ge 2 \times (n - 2) = 2n - 4 \ge n$, nên kết quả sẽ tối ưu hơn.

Theo như nhận xét trên, cách chia tối ưu là chia số $n$ thành các số $2$ và $3$. Do đó tích lớn nhất có dạng $2^i3^j$.

Đến đây có 2 cách xử lí.

### Duyệt

Ta chỉ cần duyệt qua tất cả các cặp $(i, j)$ thoả mãn $2i + 3j = n$ và cập nhật đáp án.

Độ phức tạp: $O(n)$.

https://leetcode.com/problems/integer-break/submissions/1068223706/

### Toán

Ta sẽ ưu tiên chọn $3$ hơn $2$, và 2 số $3$ hơn 3 số $2$, vì $3 > 2, 3 \times 3 > 2 \times 2 \times 2$. Như vậy, ta có 3 trường hợp theo modulo 3.

0. Nếu $n \equiv 0 \pmod{3}$, ta chọn tất cả là $3$ thì đáp án là $3^{n/3}$.
1. Nếu $n \equiv 1 \pmod{3}$, ta chọn 2 số $2$ và chọn hết đống còn lại là $3$, đáp án là $4 \times 3^{(n - 4)/3}$.
2. Nếu $n \equiv 2 \pmod{3}$, ta chọn 1 số $2$ và chọn hết đống còn lại là $3$, đáp án là $2 \times 3^{(n - 2)/3}$.

Độ phức tạp: $O(1)$.

https://leetcode.com/problems/integer-break/submissions/1068234391/