Find minimum log transportation cost

Math

42.2% acceptance

Feb 25, 2026

You are given integers n, m, and k. There are two logs of lengths n and m units, which need to be transported in three trucks where each truck can carry one log with length at most k units. You may cut the logs into smaller pieces, where the cost of cutting a log of length x into logs of length len1 and len2 is cost = len1 * len2 such that len1 + len2 = x. Return the minimum total cost to distribute the logs onto the trucks. If the logs don't need to be cut, the total cost is 0.

Solution

Rust

Time O(1)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_cutting_cost(n: i32, m: i32, k: i32) -> i64 {
    // Since n,m <= 2k, each log needs at most one cut.
    // If log fits (len <= k): no cost.
    // If log doesn't fit (len > k): cut into pieces of size (len-k) and k.
    // Cost = (len-k) * k.
    // We need to fit both logs into 3 trucks (three trucks total).
    // If both fit without cuts: cost = 0.
    // If exactly one needs a cut: cut that one, cost = (len-k)*k.
    // If both need cuts: we have 4 pieces but only 3 trucks. 
    //   One log can go uncut into 1 truck? No, if len > k it doesn't fit.
    //   We need to cut both. But 2 cuts gives 4 pieces and we only have 3 trucks.
    //   Actually, the constraint says "it is always possible", and n,m <= 2k.
    //   If both > k, we can't fit in 3 trucks after cutting!
    //   Wait: if n > k and m > k, then n <= 2k and m <= 2k mean:
    //     n > k: n in (k, 2k] -> cut into (n-k) and k. 2 pieces.
    //     m > k: similarly 2 pieces. Total 4 pieces, 3 trucks. Impossible!
    //   But the problem says it's always possible, so at most one log has length > k.
    //   Actually if one log can be cut differently... No: we must split n into pieces <= k.
    //   For n > 2k that's impossible. For k < n <= 2k, exactly 2 pieces needed.
    //   For both n,m > k: impossible to fit in 3 trucks. Constraint says always possible.
    //   So at most one log has length > k.
    
    let mut cost = 0i64;
    let k = k as i64;
    let n = n as i64;
    let m = m as i64;
    if n > k { cost += (n - k) * k; }
    if m > k { cost += (m - k) * k; }
    cost
  }
}