Minimum Total Batch Expense
Amazon● MediumNEW GRADFULLTIMEOAProblem statement
With Amazon's new innovative OptiBatch Kit users can effortlessly optimize the arrangement of their processing batches. This kit is designed to minimize the overall expense needed for efficient processing.
The process starts with an array of batches, and the objective is to reduce the total expense required. The expense is the sum of expenses needed for each batch.
Formally, given an array expense of size p, utilizing the OptiBatch Kit, users can perform operations on the array. In each operation, the user chooses two positions a and b, such that the expense of the batch at position a (expense[a]) is divisible by the expense of the batch at position b (expense[b]). When this condition is satisfied, the expense of batch a can be updated to equal the expense of batch b. This operation can be repeated as many times as possible, on different batches or positions.
An integer a is divisible by another integer b if a can be divided by b exactly, with nothing left over; for example, 6 is divisible by 3, while 7 is not.
Find the minimum total expense after applying some (possibly zero) number of operations.
Complete the function determineMinimalExpense in the editor below.
determineMinimalExpense has the following parameter:
int expense[p]: the expense array, whereexpense[a]is the expense needed for each batch
long: the minimum total expense after applying some (possibly zero) number of operations
Function
determineMinimalExpense(expense: int[]) → longExamples
Example 1
expense = [3, 6, 2, 5, 25]return = 17Let's try a series of operations by choosing the indexes for each step:
| Indexes Chosen | New Expenses | Total Expense |
|---|---|---|
| a = 1, b = 0 | [3, 3, 2, 5, 25] | 38 |
| a = 4, b = 3 | [3, 3, 2, 5, 5] | 18 |
| Indexes Chosen | New Expenses | Total Expense |
|---|---|---|
| a = 1, b = 2 | [3, 2, 2, 5, 25] | 37 |
| a = 4, b = 3 | [3, 2, 2, 5, 5] | 17 |
Note that we can never choose a = 3, b = 2 since
expense[3] = 5 is not divisible by
expense[2] = 2.
After applying all the operations in both ways we will end up with a
total expense of 18 and 17 respectively. Since
the second way yields less expense it will be chosen, hence the answer
is 17.