# Find Minimum Log Transportation Cost
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-minimum-log-transportation-cost)
Canonical: https://scaleengineer.com/dsa/problems/find-minimum-log-transportation-cost
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
---
## Problem
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.

**Example 1:**

**Input:** n = 6, m = 5, k = 5

**Output:** 5

**Explanation:**

Cut the log with length 6 into logs with length 1 and 5, at a cost equal to `1 * 5 == 5`. Now the three logs of length 1, 5, and 5 can fit in one truck each.

**Example 2:**

**Input:** n = 4, m = 4, k = 6

**Output:** 0

**Explanation:**

The two logs can fit in the trucks already, hence we don't need to cut the logs.

**Constraints:**

* `2 <= k <= 105`
* `1 <= n, m <= 2 * k`
* The input is generated such that it is always possible to transport the logs.

# Approaches
## Brute Force with Single Cut
This approach attempts to find the minimum cost by exploring the simplest cutting scenarios: making at most one cut in total. This results in either two or three final log pieces. If the original logs `n` and `m` are both no longer than `k`, no cuts are needed, and the cost is zero. Otherwise, the algorithm exhaustively tries every possible single cut on log `n` (if `m <= k`) and log `m` (if `n <= k`), checking if the resulting three pieces can all fit into trucks. It keeps track of the minimum cost found.
**Time:** O(n + m) - The algorithm involves two loops that iterate up to `n-1` and `m-1` times in the worst case. · **Space:** O(1) - The algorithm uses a constant amount of extra space.
**Pros:** Simple to understand and implement.; Correctly solves cases where at most one log is larger than `k`.
**Cons:** This approach is based on a flawed model that only considers a maximum of three final pieces. It fails to find a solution for the case where both `n > k` and `m > k`, as this would require at least two cuts, resulting in four pieces, which contradicts the model's assumption.; The time complexity is dependent on the lengths of the logs, which can be large.
### Explanation
The core idea is to check all possibilities that result in three or fewer pieces. This happens in two main situations:

1.  **Zero cuts**: If `n <= k` and `m <= k`, we have two pieces that fit in two of the three trucks. The cost is 0.
2.  **One cut**: If one log is larger than `k` but the other is not (e.g., `n > k` and `m <= k`), we can cut the larger log. We iterate through all possible cut points for the larger log and find the minimum cost among valid cuts. A cut of log `n` at `i` is valid if the resulting pieces `i` and `n-i`, along with log `m`, are all less than or equal to `k`.

This method is essentially a brute-force search over all single-cut possibilities.

```java
class Solution {
    public long minCost(int n, int m, int k) {
        if (n <= k && m <= k) {
            return 0;
        }

        long minCost = Long.MAX_VALUE;

        // Case 1: Cut log n, m is not cut
        if (m <= k) {
            for (int i = 1; i < n; i++) {
                if (i <= k && (n - i) <= k) {
                    minCost = Math.min(minCost, (long)i * (n - i));
                }
            }
        }

        // Case 2: Cut log m, n is not cut
        if (n <= k) {
            for (int i = 1; i < m; i++) {
                if (i <= k && (m - i) <= k) {
                    minCost = Math.min(minCost, (long)i * (m - i));
                }
            }
        }
        
        // This approach doesn't handle n > k and m > k, 
        // but the optimal solution will cover it.
        // If minCost is still MAX_VALUE, it means n>k and m>k, which this approach can't solve.
        // However, the problem guarantees a solution exists.
        // The optimal cut for the single-cut case is always (L-k, k), so we can optimize the loops.
        if (n > k && m <= k) {
            minCost = Math.min(minCost, (long)k * (n - k));
        }
        if (m > k && n <= k) {
            minCost = Math.min(minCost, (long)k * (m - k));
        }

        return minCost;
    }
}
```
### Algorithm
1. Initialize a variable `min_cost` to a very large value.
2. First, consider the case with no cuts. If `n <= k` and `m <= k`, the logs can be transported without any cuts. The cost is 0. This is the optimal solution in this case.
3. If the no-cut case is not possible, we must make at least one cut. This approach assumes we only need to make one total cut.
4. **Scenario A: Cut log `n`**. Iterate through all possible integer cut points `i` from `1` to `n-1`.
   - The pieces are `i`, `n-i`, and the uncut log `m`.
   - Check if all three pieces are valid, i.e., `i <= k`, `n-i <= k`, and `m <= k`.
   - If they are valid, calculate the cost `i * (n-i)` and update `min_cost = min(min_cost, i * (n-i))`. 
5. **Scenario B: Cut log `m`**. Iterate through all possible integer cut points `j` from `1` to `m-1`.
   - The pieces are `n`, `j`, and `m-j`.
   - Check if all three pieces are valid, i.e., `n <= k`, `j <= k`, and `m-j <= k`.
   - If they are valid, calculate the cost `j * (m-j)` and update `min_cost = min(min_cost, j * (m-j))`. 
6. Return the final `min_cost`.

## Analytical O(1) Approach
This approach provides a direct, constant-time solution by analytically determining the optimal cutting strategy for every possible configuration of `n`, `m`, and `k`. It correctly identifies that the minimum cost for a single cut is achieved by making the resulting pieces as unequal as possible. For the most complex case where both logs are larger than `k`, it considers a more advanced transportation model where pieces from different logs can share a truck. By analyzing the cost function, it identifies that the minimum cost must occur at one of three specific, calculable cutting points, thus avoiding any iteration.
**Time:** O(1) - The solution involves a few conditional checks and arithmetic operations, which take constant time. · **Space:** O(1) - The solution uses only a few variables for calculation, regardless of input size.
**Pros:** Extremely efficient with O(1) time complexity.; Provides a complete solution that handles all cases described by the constraints.; The logic is robust and based on mathematical optimization of the cost function.
**Cons:** The logic for the case where both logs are larger than `k` is more complex to derive and understand.; It relies on the interpretation that multiple log pieces can be combined in a single truck, which might not be immediately obvious from the problem statement.
### Explanation
The solution is a case-based analysis. The problem's guarantee that a solution always exists implies that the total length `n+m` will not exceed the total capacity `3k`, which allows for the combined packing strategy.

- **If `n <= k` and `m <= k`**: No cuts are needed. Cost is 0.
- **If `n > k` and `m <= k`**: `m` takes one truck. `n` must be cut into two pieces for the other two trucks. The optimal cut for `n` is into `n-k` and `k`. Cost is `k * (n-k)`.
- **If `m > k` and `n <= k`**: Symmetric to the above. Cost is `k * (m-k)`.
- **If `n > k` and `m > k`**: Both must be cut. This requires four pieces if transported separately. With only three trucks, two pieces must be combined. We cut `n` into `n1, n-n1` and `m` into `m1, m-m1`. We pack `n1` and `m1` together. The cost function `n1(n-n1) + m1(m-m1)` is minimized at the boundaries of the feasible region. We check the three corner points of this region which correspond to three distinct packing strategies and choose the one with the minimum cost.

```java
class Solution {
    public long minCost(int n, int m, int k) {
        // Case 1: Both logs fit without cuts.
        if (n <= k && m <= k) {
            return 0;
        }

        // Case 2: One log fits, the other needs one cut.
        // Since n, m <= 2k, one cut is sufficient to make pieces <= k.
        // The minimum cost to cut a log L > k into two pieces is k * (L-k).
        if (n > k && m <= k) {
            return (long)k * (n - k);
        }
        if (m > k && n <= k) {
            return (long)k * (m - k);
        }

        // Case 3: Both logs are greater than k.
        // This requires a more complex strategy as we need 4 pieces but have 3 trucks.
        // This implies two pieces must be combined in one truck.
        // Let's cut n into n1, n-n1 and m into m1, m-m1.
        // Let's combine n1 and m1. Truck1: {n1, m1}, Truck2: {n-n1}, Truck3: {m-m1}.
        // Constraints: n1+m1 <= k, n-n1 <= k, m-m1 <= k.
        // This implies n1 >= n-k and m1 >= m-k.
        // We need to minimize cost = n1*(n-n1) + m1*(m-m1).
        // The minimum will be at one of the vertices of the feasible region for (n1, m1).

        long cost1, cost2, cost3;

        // Strategy A: n1=n-k, m1=m-k. (Combine the smallest possible pieces from each cut).
        // Pieces are k, k, and (n-k)+(m-k). This is valid if n+m-2k <= k -> n+m <= 3k.
        cost1 = (long)k * (n - k) + (long)k * (m - k);

        // Strategy B: n1=n-k, n1+m1=k -> m1=k-(n-k) = 2k-n.
        // Pieces are k, k, and m-m1 = m-(2k-n) = n+m-2k.
        cost2 = (long)k * (n - k) + (long)(2L * k - n) * (n + m - 2L * k);

        // Strategy C: m1=m-k, n1+m1=k -> n1=k-(m-k) = 2k-m.
        // Pieces are k, k, and n-n1 = n-(2k-m) = n+m-2k.
        cost3 = (long)k * (m - k) + (long)(2L * k - m) * (n + m - 2L * k);

        return Math.min(cost1, Math.min(cost2, cost3));
    }
}
```
### Algorithm
1.  **Case 1: `n <= k` and `m <= k`**
    - Both logs fit into trucks without any cuts. The cost is `0`.

2.  **Case 2: One log is larger than `k` (e.g., `n > k` and `m <= k`)**
    - The smaller log (`m`) fits in one truck. The larger log (`n`) must be cut. Since `n <= 2k`, one cut is sufficient.
    - To minimize the cutting cost `len1 * len2` for a log of length `n`, we need to make the cut as unbalanced as possible, subject to `len1 <= k` and `len2 <= k`. The optimal pieces are `n-k` and `k`.
    - The cost is `(long)k * (n - k)`. The case `m > k` and `n <= k` is symmetric, with cost `(long)k * (m - k)`.

3.  **Case 3: `n > k` and `m > k`**
    - Both logs must be cut. This would produce at least four pieces. Since we only have three trucks, this implies that at least two pieces must share a truck, assuming their combined length is at most `k`.
    - This scenario requires cutting `n` into `n1, n-n1` and `m` into `m1, m-m1`. Two pieces, say `n1` and `m1`, are packed together. The other two, `n-n1` and `m-m1`, occupy the other two trucks.
    - The cost is `n1*(n-n1) + m1*(m-m1)`. We need to minimize this cost subject to the constraints: `n-n1 <= k`, `m-m1 <= k`, and `n1+m1 <= k`.
    - The minimum cost for this configuration occurs at one of three strategic cutting points:
        a. **Strategy 1**: Cut off `n-k` from `n` and `m-k` from `m`. The pieces are `n-k` and `k` from log `n`, and `m-k` and `k` from log `m`. We pack `n-k` and `m-k` together. Cost is `k*(n-k) + k*(m-k)`.
        b. **Strategy 2**: Cut off `n-k` from `n`. Then, to fill the truck containing `n-k` up to capacity `k`, cut off a piece of length `k-(n-k) = 2k-n` from `m`. Cost is `k*(n-k) + (2k-n)*(m-(2k-n)) = k*(n-k) + (2k-n)*(n+m-2k)`.
        c. **Strategy 3**: Symmetric to strategy 2. Cut off `m-k` from `m`, and `2k-m` from `n`. Cost is `k*(m-k) + (2k-m)*(n-(2k-m)) = k*(m-k) + (2k-m)*(n+m-2k)`.
    - The final cost is the minimum of the costs from these three strategies.

# Solutions
### Java

```java
class Solution {
public
  long minCuttingCost(int n, int m, int k) {
    int x = Math.max(n, m);
    return x <= k ? 0 : 1L * k * (x - k);
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long minCuttingCost(int n, int m, int k) {
    int x = max(n, m);
    return x <= k ? 0 : 1LL * k * (x - k);
  }
};

```

### Python

```python
class Solution:
    def minCuttingCost(self, n: int, m: int, k: int) -> int: x = max(n, m) return 0 if x <= k else k * (x - k)

```