FastPrep

Description

Solutions

Find Minimum Cost to Shift Machines

📚RELATED PROBLEMS

Memo:) The original post did not specify the company associated with the question. However, we found an identical question from Cisco. While we cannot be entirely certain that the post from 01-25-2025 originated from Cisco, the matching content suggests it is shared between Cisco and another unidentified company. Therefore, we will update the Last Seen date to 01-25-2025 to reflect this.

There are n regions where some servers are hosted. The number of machines in the i^th region is machineCount[i], where 0 ≤ i < n. It can get difficult to manage all the different regions, so the team decided to move some machines to exactly 3 regions, where the number of machines in the i^th region is given by finalMachineCount[i], where 0 ≤ i < 3.

There are two operations that can be performed:

Add or remove a machine from any existing region. The number of computers in that server should be non-zero before and after the operation. This operation costs 1 unit.

Move all machines from one region to another existing region at a cost of shiftingCost units. The now empty region is destroyed in this operation.

Find the minimum cost to shift the machines so that any 3 regions have the counts required in finalMachineCount.

Note: It is possible that there are additional machines left at the end apart from the ones placed in the final 3 regions.

🩵 Thanks a squillion, spike! 🩵

Example 1:

Input:  machineCount = [2, 4, 5, 3], finalMachineCount = [4, 4, 4], shiftingCost = 5
Output: 2 
Explanation:

On increasing the number of machines of the 4^th region by 1 and decreasing the number of machines of the 3^rd region by 1, the new machineCount = [2, 4, 4, 4]. Total cost for these operations = 1+1=2.
    
Use the 2^nd, 3^rd, and 4^th regions as the required servers, leaving behind the 1^st region.

Example 2:

Input:  machineCount = [2, 3, 5, 7], finalMachineCount = [5, 10, 5], shiftingCost = 2
Output: 2 
Explanation:

On increasing the number of machine in the 1st and 2nd regions by 1 and 2 machines respectively, the new machineCost = [2, 3, 5, 7]. Total cost for these operations = 1 + 2 = 3.

Now, moving all the machines form th 4th region to 1st, which takes shiftingCost = 2, the new machineCost = [10, 5, 5]. The cost of this operation is 2.

Therefore, the total cost = 3 +2 = 5 :)

(Can confirm that the second example & explanation & constraints are accurate and original. I'm just being a bit lazy about uploading another source image atm :)

Constraints:

3 <= n <= 10

1 <= machineCount[i], finalMachineCount[i] <= 10^6

May missing 1 or more constraints here. Will add once find the reference :)