3560. Find Minimum Log Transportation Cost
Problem Description
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.
Intuition
The goal is to fit two logs into three trucks, where each truck can carry at most k
units in length. If both logs are already less than or equal to k
, they can be loaded without any cutting or cost. If one of the logs is too long (greater than k
), we need to cut it so all resulting pieces have length at most k
. Since we have three trucks and two logs, at most one log needs to be split into two parts. The most efficient cut is to make one piece exactly k
(so it fits on one truck), and the other piece is the remainder (x - k
). The cost for such a cut, according to the problem, is k * (x - k)
. This way, we achieve the minimum possible cost while ensuring all logs or log pieces can be transported.
Solution Approach
First, check if both logs have lengths less than or equal to k
. If so, no cuts are required, so the answer is 0
.
If one of the logs is longer than k
, it must be cut into two pieces so that both are at most k
units in length. Since there are three trucks and two logs, only split one log: the longer one.
Let the longer log's length be x
. The optimal way to cut it is to create one piece of length exactly k
(maximizing the utilization of the truck) and the other piece as x - k
. The cost for this cut, by the problem statement, is k * (x - k)
.
The solution follows these steps:
- Let
x = max(n, m)
. - If
x <= k
, return0
. - Otherwise, return
k * (x - k)
.
No complex data structures or algorithms are required since this is solved with a simple mathematical calculation.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Suppose n = 6
, m = 3
, and k = 4
.
Step 1: Check the lengths of the logs:
- Log 1: 6 units
- Log 2: 3 units Both must be transported in trucks of maximum length 4.
Step 2: Is either log longer than 4?
- Log 2 (3) ≤ 4: fits in a truck
- Log 1 (6) > 4: too long, needs cutting
Step 3: We cut the longer log (6 units) into two pieces:
- One piece of length exactly 4 (for one truck)
- The other, the remainder: 6 - 4 = 2 (fits in another truck)
Step 4: Calculate the cost:
- Cost = 4 * 2 = 8
Summary: The minimum total cost is 8. The three trucks will carry logs of lengths 4, 2, and 3 units respectively.
Solution Implementation
1class Solution:
2 def minCuttingCost(self, n: int, m: int, k: int) -> int:
3 # Determine the larger dimension
4 max_side = max(n, m)
5 # If the largest side is less than or equal to k, no cutting is needed
6 if max_side <= k:
7 return 0
8 # Otherwise, the cost is k * (max_side - k)
9 return k * (max_side - k)
10
1class Solution {
2 // Finds the minimum cutting cost to reduce the longer side of a rectangle to at most k
3 public long minCuttingCost(int n, int m, int k) {
4 // Determine the longer side of the rectangle
5 int maxSide = Math.max(n, m);
6
7 // If the longer side is already less than or equal to k, no cost is required
8 if (maxSide <= k) {
9 return 0;
10 }
11 // Otherwise, cost is calculated as k times the number of cuts needed (maxSide - k)
12 return 1L * k * (maxSide - k);
13 }
14}
15
1class Solution {
2public:
3 // This function calculates the minimum cutting cost.
4 // n: length of the first side,
5 // m: length of the second side,
6 // k: maximum permitted side after cutting.
7 long long minCuttingCost(int n, int m, int k) {
8 // Find the larger of n and m
9 int maxSide = std::max(n, m);
10
11 // If the maximum side is less than or equal to k, no cut is needed
12 if (maxSide <= k) {
13 return 0;
14 }
15
16 // If a cut is needed, the cost is k * (maxSide - k)
17 // Cast to long long to avoid integer overflow
18 return 1LL * k * (maxSide - k);
19 }
20};
21
1/**
2 * Calculates the minimum cutting cost for a rectangle of size n x m,
3 * given that a cut can divide the longer side by at most k units.
4 *
5 * @param n - The height of the rectangle
6 * @param m - The width of the rectangle
7 * @param k - The maximum cut length allowed for the longer side
8 * @returns The minimum cost to cut the rectangle so that neither side exceeds k
9 */
10function minCuttingCost(n: number, m: number, k: number): number {
11 // Determine the longer side of the rectangle
12 const maxSide: number = Math.max(n, m);
13
14 // If the longer side is already within the allowed size, no cost is needed
15 if (maxSide <= k) {
16 return 0;
17 }
18
19 // Otherwise, compute the minimum cost required to cut the rectangle
20 // The cost is k for each cut, and the number of cuts is (maxSide - k)
21 return k * (maxSide - k);
22}
23
24// Example usage:
25// const result = minCuttingCost(8, 5, 4);
26// console.log(result); // Output: 16
27
Time and Space Complexity
The time complexity of the code is O(1)
because it only uses a constant number of operations regardless of the input values.
The space complexity is also O(1)
since it only uses a constant amount of additional space for variable storage.
What's the relationship between a tree and a graph?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Don’t Miss This!