FastPrep
Problem · Array

Cutting Metal Surplus

● MediumFULLTIMEINTERNOA

The owner of a construction company has a surplus of rods of arbitrary lengths. A local contractor offers to buy any of the surplus, as long as all the rods have the same exact integer length, referred to as saleLength. The number of sellable rods can be increased by cutting each rod zero or more times, but each cut has a cost denoted by costPerCut. After all cuts have been made, any leftover rods having a length other than saleLength must be discarded for no profit. The owner's total profit for the sale is calculated as:

totalProfit = totalUniFormRods * saleLength * salePrice - totalCuts * costPerCut

where totalUniformRods is the number of sellable rods, salePrice is the per unit length price that the contractor agrees to pay, and the totalCuts is the total number of times the rods needed to be cut.

Function Description

Complete the function maxProfit in the editor.

maxProfit has the following parameter(s):

  • costPerCut: cost to make a cut
  • salePrice : per unit length sales price
  • lengths[n]: integer rod lengths

    • Returns

  • int: maximum possible profit

    • Examples
    01 · Example 1
    lengths = [30, 59, 110]
costPerCut = 1
salePrice = 10
return = 1913
    Example 1 illustration
    Working through the first stanza, length = 30, it is the same length as the first rod, so no cuts are required and there is 1 piece. For the second rod, cut and discard the excess 29 unit rod. No more cuts are necessary and another 1 piece is left to sell. Cut 20 units off the 110 unit rod to discard leaving 90 units, then make two more cuts to have 3 more pieces to sell. Finally sell 5 totalUniformRods, costPerCut = 1 per cut, or 4. Total revenue = 1500 - 4 = 1496. The maximum revenue among these tests is obtained at length 5 for 1913.
    02 · Example 2
    lengths = [26, 103, 59]
costPerCut = 100
salePrice = 10
return = 1230
    Example 2 illustration
    Since costPerCut = 100, cuts are expensive and must be minimal. The optimal rod length for maximizing profit is 51, and the rods are cut as shown: lengths[0] = 26: Discard this rod entirely. lengths[1] = 103: Cut off a piece of length 1 and discard it, resulting in a rod of length 102. Then, cut this rod into 2 pieces of length 51. lengths[2] = 59: Cut off a piece of length 8 and discard it, resulting in a rod of length 51. After performing totalCuts = (0) + (1 + 1) + (1) = 3 cuts, there are totalUniformRods = 0 + 2 + 1 = 3 pieces of length saleLength = 51 that can be sold at salePrice = 10 each. This yields a total profit of salePrice * totalUniformRods * saleLength - totalCuts * costPerCut = 10 * 3 * 51 - 3 * 100 = 1230.
    Constraints
  • 1 <= n <= 50
  • 1 <= lengths[i] <= 104
  • 1 <= salePrice, costPerCut <= 100
    • More Goldman Sachs problems
    drafts saved locally
    public int maxProfit(int[] lengths, int costPerCut, int salePrice) {
    // write your code here
}
    lengths[30, 59, 110]
    costPerCut1
    salePrice10
    expected1913
    sign in to submit