3857. Minimum Cost to Split into Ones

MediumMathDynamic Programming

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.

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

In simple terms, you start with the single number n, and you need to keep breaking it down until you are left with n separate 1s. Each time you break a number into two parts, you pay a cost equal to the product of those two parts. Your goal is to find the smallest possible sum of all these costs.

For example, if you split n into a and b, you add a * b to your total cost, and then you continue splitting a and b (if they are greater than 1) in the same way, until every piece is a 1.

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.

The total cost is invariant and equals n*(n-1)/2 by combinatorial pairing argument, reducing to a closed-form arithmetic formula.

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 cases to see what happens.

Consider splitting n into a and b. The immediate cost is a * b. After this, we need to break down a into a ones and b into b ones. This suggests we can think recursively, but let's look for a pattern instead.

Let's try a small example with n = 4:

Option 1: Split 4 into 2 and 2 (cost 4). Then split each 2 into 1 and 1 (cost 1 each). Total: 4 + 1 + 1 = 6.
Option 2: Split 4 into 1 and 3 (cost 3). Then split 3 into 1 and 2 (cost 2). Then split 2 into 1 and 1 (cost 1). Total: 3 + 2 + 1 = 6.

Interestingly, both options give the same result: 6. This hints that the total cost is always the same, no matter how we split.

We can understand why with a clever observation. Think of the n ones as n separate points. To fully break n down into all its individual ones, every pair of those final ones must be "separated" exactly once during some split. When we split a group into parts a and b, the cost a * b counts exactly the number of pairs where one element ends up in the a side and the other ends up in the b side.

Since every pair of the n final ones gets separated exactly once across the entire process, the total cost equals the total number of pairs we can form from n items, which is:

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

This explains why the order does not matter, and gives us a direct formula. The answer is simply:

n * (n - 1) / 2

Pattern Learn more about Math and Dynamic Programming patterns.

Solution Approach

Solution 1: Math

Based on the intuition that the total cost is fixed regardless of how we split, we can build the cheapest path step by step to confirm and compute the formula directly.

To minimize the total cost, we first split n into 1 and n - 1, with a cost of 1 * (n - 1) = n - 1. Next, we split n - 1 into 1 and n - 2, with a cost of 1 * (n - 2) = n - 2.

We continue this process until we split 2 into 1 and 1, with a cost of 1 * 1 = 1. Therefore, the total cost is:

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

This is simply the sum of the first n - 1 positive integers, which has a well-known closed form.

Since no data structures or loops are required, the implementation reduces to a single arithmetic expression. We use integer division // to ensure the result is an integer, which is valid because n * (n - 1) is always even (one of two consecutive integers must be even).

class Solution:
    def minCost(self, n: int) -> int:
        return n * (n - 1) // 2

The time complexity is O(1), and the space complexity is O(1), since we only perform a constant number of arithmetic operations and use no extra space.

Example Walkthrough

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

We start with the single number 5, and our goal is to break it down into five separate 1s while paying the minimum total cost. Following the strategy from Solution 1, we always peel off a single 1 at each step.

Step 1: Split 5 into 1 and 4.

Cost: 1 * 4 = 4
Remaining piece to break down: 4
Running total: 4

Step 2: Split 4 into 1 and 3.

Cost: 1 * 3 = 3
Remaining piece to break down: 3
Running total: 4 + 3 = 7

Step 3: Split 3 into 1 and 2.

Cost: 1 * 2 = 2
Remaining piece to break down: 2
Running total: 7 + 2 = 9

Step 4: Split 2 into 1 and 1.

Cost: 1 * 1 = 1
Remaining piece to break down: none (all pieces are now 1)
Running total: 9 + 1 = 10

At this point we have five 1s, and the accumulated cost is 10.

Verifying with the formula:

The costs we summed were 4 + 3 + 2 + 1, which is the sum of the first n - 1 = 4 positive integers. Applying the closed form:

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

This matches our step-by-step total of 10.

Confirming order doesn't matter:

Suppose instead we split 5 into 2 and 3 first.

Split 5 → 2 + 3: cost 2 * 3 = 6
Split 2 → 1 + 1: cost 1 * 1 = 1
Split 3 → 1 + 2: cost 1 * 2 = 2
Split 2 → 1 + 1: cost 1 * 1 = 1
Total: 6 + 1 + 2 + 1 = 10

We arrive at the same answer of 10, confirming that the total cost is fixed regardless of the splitting order. This is because each of the C(5, 2) = 10 pairs among the five final 1s gets separated exactly once during the process.

Solution Implementation

1class Solution:
2    def minCost(self, n: int) -> int:
3        # Compute the sum of the first (n - 1) natural numbers: 0 + 1 + 2 + ... + (n - 1)
4        # This uses the arithmetic series formula: sum = n * (n - 1) / 2
5        # Integer division (//) is used to ensure the result is an int rather than a float.
6        return n * (n - 1) // 2
7

1class Solution {
2    /**
3     * Calculates the minimum cost.
4     * The result follows the formula for the sum of the first (n - 1) natural numbers:
5     * n * (n - 1) / 2, which equals 0 + 1 + 2 + ... + (n - 1).
6     *
7     * @param n the input count
8     * @return the minimum cost computed from the formula
9     */
10    public int minCost(int n) {
11        // Apply the arithmetic series sum formula: n * (n - 1) / 2
12        return n * (n - 1) / 2;
13    }
14}
15

1class Solution {
2public:
3    // Computes the minimum cost based on the given size n.
4    // The formula n * (n - 1) / 2 corresponds to the sum of the
5    // first (n - 1) natural numbers, i.e. the number of unique
6    // pairs that can be formed from n elements (n choose 2).
7    int minCost(int n) {
8        // Calculate the triangular number: 0 + 1 + 2 + ... + (n - 1)
9        int result = n * (n - 1) / 2;
10        return result;
11    }
12};
13

1/**
2 * Calculates the minimum cost based on the given count.
3 * The formula computes the sum of integers from 0 to (n - 1),
4 * which equals n * (n - 1) / 2.
5 *
6 * @param n - The total number of elements.
7 * @returns The minimum cost as a number.
8 */
9function minCost(n: number): number {
10    // Multiply n by (n - 1) to get the product of consecutive integers.
11    const product: number = n * (n - 1);
12
13    // Right shift by 1 is equivalent to integer division by 2,
14    // yielding the triangular number (sum of 0 to n - 1).
15    const result: number = product >> 1;
16
17    return result;
18}
19

Time and Space Complexity

Time Complexity: O(1). The function performs a single arithmetic computation n * (n - 1) // 2, which involves a fixed number of operations (one multiplication, one subtraction, and one integer division) regardless of the value of n. Therefore, the execution time is constant.
Space Complexity: O(1). The function uses only a constant amount of extra space to store intermediate results of the arithmetic expression and the return value. No additional data structures that scale with the input size are allocated.

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

Common Pitfalls

Pitfall 1: Overthinking the Problem with Recursion or DP

The most common pitfall is assuming that the way you split matters, leading you to write an expensive recursive or dynamic programming solution that tries every possible split point to find the "minimum."

A typical (and unnecessary) attempt looks like this:

class Solution:
    def minCost(self, n: int) -> int:
        from functools import lru_cache

        @lru_cache(None)
        def dfs(x):
            if x == 1:
                return 0
            best = float('inf')
            for a in range(1, x):
                b = x - a
                best = min(best, a * b + dfs(a) + dfs(b))
            return best

        return dfs(n)

Why this is a pitfall: The total cost is actually invariant—it is the same no matter how you split. The proof: every final cost can be viewed as counting each pair of 1s exactly once, because each pair gets "separated" at exactly one split, contributing 1 to that split's product. With n ones, the number of pairs is C(n, 2) = n * (n - 1) / 2.

So all that work yields the same answer as the O(1) formula, but with O(n^2) time (with memoization) or exponential time (without), and it will TLE or stack overflow for large n.

Solution: Recognize the invariance and use the closed form directly:

return n * (n - 1) // 2

Pitfall 2: Integer Overflow in Fixed-Width Languages

In Python this is a non-issue because integers are arbitrary-precision. However, if you port this to C++, Java, or Go, the product n * (n - 1) can overflow a 32-bit integer for large n (around n > 65535).

// Buggy: int overflow
int minCost(int n) {
    return n * (n - 1) / 2;   // overflows for large n
}

Solution: Use a 64-bit type (long / long long) for the multiplication:

long minCost(int n) {
    return (long) n * (n - 1) / 2;
}

Pitfall 3: Using Floating-Point Division

Writing n * (n - 1) / 2 with the / operator in Python returns a float, which can cause precision loss for very large n and yields a wrong type (e.g., 6.0 instead of 6).

return n * (n - 1) / 2   # returns float, may lose precision for large n

Solution: Always use integer division //. This is safe because n * (n - 1) is the product of two consecutive integers, so one of them is always even—the result is guaranteed to be exact:

return n * (n - 1) // 2

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 of these properties could exist for a graph but not a tree?

Contain cycles

There are multiple ways to traverse

Connected

Has no cycle

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering