Minimum cost to split into ones

Math Dynamic Programming

83.2% acceptance

Mar 15, 2026

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.

Solution

Rust

Time O(1)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_cost(n: i32) -> i32 {
    // The minimum cost to split n into n ones is always n*(n-1)/2.
    // Proof: splitting x into 1 and x-1 costs x-1. Total = (n-1)+(n-2)+...+1 = n*(n-1)/2.
    // Any other split gives same or higher cost. Actually it's always equal:
    // The total cost to split n into n ones is always n*(n-1)/2 regardless of strategy.
    // This can be proven: each pair of final 1s contributes exactly 1 to the total cost.
    // There are C(n,2) = n*(n-1)/2 such pairs.
    n * (n - 1) / 2
  }
}