3958. Minimum Cost to Split into Ones II 🔒

MediumMath

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer n.

In one operation, you may split an integer x into two positive integers a and b such that a + b = x. The cost of this operation is a * b.

Your task is to repeatedly perform these split operations until the integer n is broken down completely into n ones. Each split adds its own cost (a * b) to the running total.

Return the minimum total cost required to split the integer n into n ones.

For example, if you split n into 1 and n - 1, the cost of that single operation is 1 * (n - 1) = n - 1. You then continue splitting the resulting pieces until every value equals 1. The goal is to choose the splits so that the sum of all operation costs is as small as possible.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Math / Bit Manipulation?

This problem maps to Math / Bit Manipulation through a short path in the full flowchart.

A mathematical formula or identity computes the answer directly.

Open in Flowchart

Intuition

At first glance, it seems like the order in which we split the number might affect the total cost. So let's explore a few splitting strategies to understand what's really happening.

Take a small example, say n = 4. Let's try two different splitting orders:

Strategy A: Split 4 into 1 and 3 (cost 1 * 3 = 3), then split 3 into 1 and 2 (cost 1 * 2 = 2), then split 2 into 1 and 1 (cost 1 * 1 = 1). Total cost = 3 + 2 + 1 = 6.
Strategy B: Split 4 into 2 and 2 (cost 2 * 2 = 4), then split each 2 into 1 and 1 (cost 1 * 1 = 1 each). Total cost = 4 + 1 + 1 = 6.

Interestingly, both strategies give the same total cost of 6. This is a strong hint that no matter how we choose to split the number, the total cost is always the same!

Why does this happen? Think of it this way: every time we split a group, we are essentially deciding which pairs of the final n ones get "separated" at this step. By the time everything is broken down into single ones, every pair of the n ones has been separated exactly once. Each separation between two ones contributes exactly 1 to the total cost (because when one item from a group of size a and another item from a group of size b get split apart, the cost a * b counts every such pair).

So the total cost equals the number of ways to pick 2 ones out of n, which is the combination C(n, 2):

C(n, 2) = n * (n - 1) / 2

This means we don't need any complex dynamic programming or recursion. The answer is simply this fixed formula, and the order of splitting never matters.

Pattern Learn more about Math patterns.

Solution Approach

Solution 1: Mathematics

Based on the intuition above, we know the total cost is always the same regardless of the splitting order, so we can pick the simplest splitting pattern to confirm the formula.

To minimize the cost, we first split n into 1 and n - 1, which costs n - 1; then split n - 1 into 1 and n - 2, which costs n - 2. Following this pattern, the total cost is accumulated as 1 + 2 + ... + (n - 1).

This is just the sum of the first n - 1 positive integers, which has a well-known closed-form formula:

1 + 2 + ... + (n - 1) = n * (n - 1) / 2

So the implementation reduces to a single line: we directly compute and return n * (n - 1) // 2. We use integer division // because the result n * (n - 1) is always even (one of two consecutive integers is even), so the division produces an exact integer.

No loops, recursion, or extra data structures are needed. The time complexity is O(1) and the space complexity is O(1).

Example Walkthrough

Let's trace through the solution approach using a small example with n = 5.

Goal: Break 5 down into five 1s while minimizing the total splitting cost.

Applying the simplest splitting pattern (split off a 1 each time):

We follow the strategy from Solution 1, where we repeatedly split n into 1 and n - 1:

Step	Split	Cost (`a * b`)	Running Total
1	`5 → 1 + 4`	`1 * 4 = 4`	`4`
2	`4 → 1 + 3`	`1 * 3 = 3`	`7`
3	`3 → 1 + 2`	`1 * 2 = 2`	`9`
4	`2 → 1 + 1`	`1 * 1 = 1`	`10`

The total cost accumulates as 4 + 3 + 2 + 1 = 10.

Verifying with a different splitting order (split into balanced halves):

To confirm the order doesn't matter, let's try a different strategy:

Step	Split	Cost (`a * b`)	Running Total
1	`5 → 2 + 3`	`2 * 3 = 6`	`6`
2	`3 → 1 + 2`	`1 * 2 = 2`	`8`
3	`2 → 1 + 1`	`1 * 1 = 1`	`9`
4	`2 → 1 + 1`	`1 * 1 = 1`	`10`

Again, the total cost is 6 + 2 + 1 + 1 = 10. Same result!

Confirming with the formula:

Using the closed-form formula n * (n - 1) / 2:

5 * (5 - 1) / 2 = 5 * 4 / 2 = 20 / 2 = 10

Why this matches the intuition:

There are C(5, 2) = 10 distinct pairs among the five final 1s. Each pair gets separated exactly once across all splits, and each separation contributes exactly 1 to the total cost. No matter which splitting order we choose, we always end up paying for those same 10 pair separations — giving a total cost of 10.

This demonstrates that we can skip all the splitting simulation and directly return n * (n - 1) // 2.

Solution Implementation

1class Solution:
2    def minCost(self, n: int) -> int:
3        # Calculate the sum of the arithmetic series: 0 + 1 + 2 + ... + (n - 1)
4        # This is equivalent to the combination formula C(n, 2) = n * (n - 1) / 2
5        # Using integer division (//) to ensure the result is an integer
6        return n * (n - 1) // 2
7

1class Solution {
2    /**
3     * Calculates the minimum cost.
4     * The result is the sum of the first (n - 1) natural numbers,
5     * computed using the arithmetic series formula: n * (n - 1) / 2.
6     *
7     * @param n the input size
8     * @return the minimum cost as a long value
9     */
10    public long minCost(int n) {
11        // Multiply by 1L to force long arithmetic and prevent integer overflow
12        return 1L * n * (n - 1) / 2;
13    }
14}
15

1class Solution {
2public:
3    // Computes the minimum cost, defined as the sum of the first (n - 1) integers:
4    // 0 + 1 + 2 + ... + (n - 1), which equals n * (n - 1) / 2.
5    long long minCost(int n) {
6        // Use 1LL to promote the multiplication to long long and avoid integer overflow.
7        long long total_cost = 1LL * n * (n - 1) / 2;
8        return total_cost;
9    }
10};
11

1/**
2 * Calculates the minimum cost based on the given count.
3 *
4 * The formula n * (n - 1) / 2 computes the sum of the first (n - 1)
5 * natural numbers, which is equivalent to the number of unique pairs
6 * that can be formed from n items (the combination C(n, 2)).
7 *
8 * @param n - The total number of items.
9 * @returns The minimum cost as a number.
10 */
11function minCost(n: number): number {
12    // Multiply n by (n - 1) to get the product of consecutive integers,
13    // then divide by 2 to obtain the triangular number / pair count.
14    const cost: number = (n * (n - 1)) / 2;
15
16    // Return the computed minimum cost.
17    return cost;
18}
19

Time and Space Complexity

Time Complexity: O(1). The function performs a single arithmetic computation n * (n - 1) // 2, which consists of one multiplication, one subtraction, and one integer division. These operations execute in constant time regardless of the input value n, so the overall time complexity is O(1).
Space Complexity: O(1). The function only computes and returns a single value without allocating any additional data structures whose size depends on the input. No extra space scales with n, so the space complexity is O(1).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Trying to Simulate the Splitting Process

The most common mistake is assuming that the splitting order affects the total cost, leading you to write recursive or greedy simulation code to "search" for the optimal sequence of splits.

# Incorrect / Overcomplicated approach
class Solution:
    def minCost(self, n: int) -> int:
        memo = {}
        def dfs(x):
            if x == 1:
                return 0
            if x in memo:
                return memo[x]
            best = float('inf')
            for a in range(1, x):
                b = x - a
                best = min(best, a * b + dfs(a) + dfs(b))
            memo[x] = best
            return best
        return dfs(n)

Why it's a problem: This approach is exponential (or expensive even with memoization) and is completely unnecessary. The key insight is that every valid splitting sequence yields the exact same total cost. You can prove this by induction: no matter how you partition n into n ones, the sum of all a * b costs always equals C(n, 2). Because the result is split-order independent, there is no "minimum" to search for—any order works.

Solution: Trust the mathematical invariant and use the closed-form formula n * (n - 1) // 2.

Pitfall 2: Using Floating-Point Division

Writing / instead of // introduces floating-point results and precision errors for large n.

# Incorrect
return n * (n - 1) / 2   # returns a float, e.g., 4950.0 instead of 4950

Why it's a problem: The / operator returns a float, which mismatches the expected integer return type. For very large n, floating-point can also lose precision and produce wrong values.

Solution: Use integer division //. Since n and n - 1 are consecutive integers, one of them is always even, so n * (n - 1) is guaranteed to be divisible by 2 with no remainder.

return n * (n - 1) // 2

Pitfall 3: Overlooking the Base Case `n = 1`

When n = 1, the integer is already a single 1, so no splits are needed and the cost should be 0.

Why it's a problem: If you assume the formula needs special handling for small inputs, you might add unnecessary conditional branches.

Solution: The formula handles this naturally. For n = 1, 1 * (1 - 1) // 2 = 0, which is exactly the correct answer—no special casing required.

Pitfall 4: Integer Overflow in Other Languages

While Python integers have arbitrary precision, porting this solution to languages like Java or C++ can cause overflow.

Why it's a problem: For large n, the product n * (n - 1) may exceed the range of a 32-bit integer.

Solution: In such languages, use a 64-bit type (e.g., long in Java) for the multiplication to avoid overflow before performing the division.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Depth-First Search

Breadth-First Search

Binary Search

Priority Queue

I don't know