Minimum Total Batch Expense
Learn this problem
AmazonNEW GRADFULLTIMEOAProblem statement
🦁 Source Update Note · 2026-07-17
The EffiBin era is over. Long live Minimum Total Batch Expense. The problem has returned to the Circle of Source Fidelity, with its terminology, function signature, example, and visible requirements fully aligned with the latest official source.
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.
Function
determineMinimalExpense(expense: int[]) → long
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
Returns
long: the minimum total expense after applying some (possibly zero) number of operations
Examples
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.