Tap here to switch tabs
Problem
Submissions

Problem: Minimum Cost to Split into Ones II

Minimum Cost to Split into Ones II starts with one integer and repeatedly splits values greater than one into two positive parts. Return the minimum total cost when each split costs the product of its parts.

Statement

You are given an integer n. Initially, you have a single integer n.

In each operation, you can pick any integer x where x>1x > 1 from the current collection and split it into two positive integers a and b such that a+b=xa + b = x. The cost of performing this operation is a×ba \times b.

You repeat this process until all numbers in the collection are equal to 11.

Return the minimum total cost needed to split n entirely into ones.

Constraints:

  • 1≤1 \leq n ≤5×107\leq 5 \times 10^7

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Minimum Cost to Split into Ones II

Minimum Cost to Split into Ones II starts with one integer and repeatedly splits values greater than one into two positive parts. Return the minimum total cost when each split costs the product of its parts.

Statement

You are given an integer n. Initially, you have a single integer n.

In each operation, you can pick any integer x where x>1x > 1 from the current collection and split it into two positive integers a and b such that a+b=xa + b = x. The cost of performing this operation is a×ba \times b.

You repeat this process until all numbers in the collection are equal to 11.

Return the minimum total cost needed to split n entirely into ones.

Constraints:

  • 1≤1 \leq n ≤5×107\leq 5 \times 10^7