Find Minimum Log Transportation Cost - Practice Coding Problems

Find Minimum Log Transportation Cost - Problem

Math Easy

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.

Input & Output

Example 1 — Basic Case

$ Input: n = 7, m = 4, k = 3

› Output: 21

💡 Note: Log n=7: Cut into pieces [3,3,1]. Cost = 3×4 + 3×1 = 15. Log m=4: Cut into pieces [3,1]. Cost = 3×1 = 3. Total = 15 + 6 = 21.

Example 2 — No Cuts Needed

$ Input: n = 3, m = 2, k = 5

› Output: 0

💡 Note: Both logs fit in trucks without cutting since 3 ≤ 5 and 2 ≤ 5. Total cost = 0.

Example 3 — One Log Needs Cutting

$ Input: n = 8, m = 3, k = 4

› Output: 16

💡 Note: Log n=8: Cut into [4,4]. Cost = 4×4 = 16. Log m=3: No cut needed. Total = 16.

Constraints

1 ≤ n, m, k ≤ 1000
We have exactly 3 trucks available
Each truck can carry at most one log

Visualization

Tap to expand

Understanding the Visualization

Input

Two logs of lengths n=7, m=4 with truck capacity k=3

Process

Cut logs to fit: minimize total cutting cost

Output

Minimum cost = 21

Key Takeaway

🎯 Key Insight: Cut pieces of maximum size k from the end to minimize total cost

Asked in

G Google 25 M Microsoft 20 A Amazon 15

The key insight is to cut logs optimally by removing pieces of maximum size k from the end. The mathematical approach gives O(1) time per log. Best approach uses the formula: while remaining > k, cut piece of size k with cost = k × remaining_after_cut. Time: O(1), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Formula	O(1)	O(1)	Use mathematical insight to calculate minimum cost directly
Memoization - Cache Results	O(n² + m²)	O(n + m)	Use memoization to avoid recalculating costs for same log lengths
Brute Force - Try All Cut Combinations	O(2^(n+m))	O(n+m)	Try every possible way to cut both logs and find minimum cost

Mathematical Formula — Algorithm Steps

Check if log length ≤ k (no cut needed)
Calculate number of pieces needed: ceil(length/k)
Calculate minimum cuts: pieces - 1
Use formula to compute total cost

Visualization

Tap to expand

Step-by-Step Walkthrough

Identify Pattern

Cut pieces of size k from the end

Calculate Cost

Each cut: cost = cut_piece × remaining

Sum Costs

Total = sum of all cut costs

Code -

solution.c — C

#include <stdio.h>

int minCostToCut(int length, int k) {
    if (length <= k) {
        return 0;
    }
    
    int totalCost = 0;
    int remaining = length;
    
    while (remaining > k) {
        int cutSize = k;
        remaining -= cutSize;
        totalCost += cutSize * remaining;
    }
    
    return totalCost;
}

int solution(int n, int m, int k) {
    return minCostToCut(n, k) + minCostToCut(m, k);
}

int main() {
    int n, m, k;
    scanf("%d", &n);
    scanf("%d", &m);
    scanf("%d", &k);
    printf("%d\n", solution(n, m, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Simple arithmetic operations for each log

✓ Linear Growth

Space Complexity

O(1)

Only uses constant extra variables

✓ Linear Space

23.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Formula — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler