Maximize Profit From Cutting Rods
Company: Anduril
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an array `lengths` where `lengths[i]` is the length of the `i`-th rod, determine the maximum profit obtainable by choosing a single integer `saleLength` and cutting rods to produce pieces of exactly that length.
Rules:
- You must choose one positive integer `saleLength` and use that same target length for all rods you decide to process.
- A rod of length `L` can produce `k = floor(L / saleLength)` pieces of length `saleLength`.
- Any leftover length `L % saleLength` is discarded.
- Each produced piece earns revenue `saleLength * salePrice`.
- Each cut costs `costPerCut`.
- If `L` is exactly divisible by `saleLength` and produces `k` pieces, then it requires `k - 1` cuts.
- Otherwise, producing `k` pieces requires `k` cuts.
- You may choose to discard any rod entirely if processing it would reduce profit.
Return the maximum total profit over all possible integer values of `saleLength`.
Function signature:
```python
def maxProfit(costPerCut, salePrice, lengths):
pass
```
Parameters:
- `costPerCut`: integer cost of making one cut
- `salePrice`: integer revenue per unit length sold
- `lengths`: list of positive integers representing rod lengths
Return:
- An integer representing the maximum achievable profit.
Quick Answer: This question evaluates algorithmic optimization and discrete cost-benefit analysis, testing skills in integer parameter exploration, profit modeling, and efficient aggregation across input arrays.
You are given a list of rod lengths. You must choose one positive integer `saleLength` and use that same target length for every rod you decide to process.
For a rod of length `L`:
- It can produce `k = L // saleLength` pieces of exactly `saleLength`.
- Any leftover `L % saleLength` is discarded.
- Each produced piece earns `saleLength * salePrice` in revenue.
- Each cut costs `costPerCut`.
- If `L` is exactly divisible by `saleLength`, producing `k` pieces requires `k - 1` cuts.
- Otherwise, producing `k` pieces requires `k` cuts.
You may also choose to discard any rod entirely if processing it would reduce profit.
Return the maximum total profit over all possible integer values of `saleLength`.
Implement the function as `solution(costPerCut, salePrice, lengths)`.
Constraints
- 0 <= len(lengths) <= 2000
- 1 <= lengths[i] <= 10000
- 0 <= costPerCut <= 10000
- 1 <= salePrice <= 10000
Examples
Input: (2, 5, [5, 5, 5])
Expected Output: 75
Explanation: Choose `saleLength = 5`. Each rod produces one piece, needs no cuts, and earns `5 * 5 = 25`. Total profit is `25 + 25 + 25 = 75`.
Input: (35, 3, [20, 11, 11])
Expected Output: 66
Explanation: Choose `saleLength = 11`. Each rod of length 11 earns 33 with no cuts. The rod of length 20 would produce one piece but require one cut, giving `33 - 35 = -2`, so it is discarded. Total profit is `33 + 33 = 66`.
Input: (4, 7, [])
Expected Output: 0
Explanation: There are no rods to process, so the maximum profit is 0.
Input: (3, 2, [8, 5, 8])
Expected Output: 32
Explanation: Choose `saleLength = 8`. Each rod of length 8 produces one piece with no cuts, earning 16 each. The rod of length 5 cannot produce any piece. Total profit is `16 + 16 = 32`.
Input: (2, 2, [1])
Expected Output: 2
Explanation: Choose `saleLength = 1`. The single rod produces one piece, requires no cuts, and earns `1 * 2 = 2`.
Input: (1, 2, [9, 10, 10])
Expected Output: 52
Explanation: Choose `saleLength = 9`. The rod of length 9 earns 18 with no cuts. Each rod of length 10 produces one piece of length 9, needs one cut, and earns `18 - 1 = 17`. Total profit is `18 + 17 + 17 = 52`.
Hints
- Try every possible `saleLength` from 1 up to the longest rod. For each choice, compute the profit contribution of every rod independently.
- For a fixed `saleLength`, only include a rod if its individual profit is positive. Otherwise, discard it.