CISCO Online Assessment

A. Find Machine Count

Problem Description

There are n regions where servers are hosted. The number of machines in the i-th region is given by machineCount[i], where 0 <= i < n. Managing all these regions can be challenging, so the team decided to move some machines to exactly 3 regions. The number of machines in the i-th of these 3 target regions is given by finalMachineCount[i], where 0 <= i < 3.

There are two operations that can be performed:

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

• Move All Machines: 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.

  Objective: Find the minimum cost to shift the machines so that any 3 regions have the counts required infinalMachineCount.

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

  Example

  Input:

  • n = 4

  • machineCount = [2, 3, 5, 7]

  • finalMachineCount = [5, 10, 5]

  • shiftingCost = 2

    Output:

    • 5

      Explanation:

      1. Increase the number of machines in the 1st and 2nd regions by 1 and 2 machines respectively. The newmachineCount = [3, 5, 5, 7]. Total cost for these operations is1 + 2 = 3.

      2. Move all the machines from the fourth region to the first region, which takesshiftingCost = 2. The newmachineCount = [10, 5, 5]. The cost of this operation is 2.

Total Cost = 3 + 2 = 5

Function Description

Complete the function getMinimumCost:

            int getMinimumCost(int machineCount[], int finalMachineCount[], int shiftingCost);

---

Parameters:

• int machineCount[n]: The initial number of machines in the regions.

• int finalMachineCount[3]: The final number of machines required in the 3 regions.

• int shiftingCost: The cost to move all machines from one region to another.

Returns:

• int: The minimum cost to move machines into 3 regions.

Constraints:

1. 3 <= n <= 10

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

3. 1 <= shiftingCost <= 10^6

Sample Cases

Sample Case 0

Input:

4
2 4 5 3
3
4 4 4
5

Output:

2

Explanation:

Increase the number of machines in the 4th region by 1 and decrease the number of machines in the 3rd region by 1. The newmachineCount = [2, 4, 4, 4]. Total cost for these operations is1 + 1 = 2. Use the 2nd, 3rd, and 4th regions as the required servers, leaving behind the first region.

Sample Case 1

Input:

5
5 10 15 20 25
3
20 20 20
3

Output:

8

Explanation:

On increasing the number of machines in the 5th region by 5, the new machine count = [5, 10, 15, 20, 20]. Total cost required for these operations = 5.
Now, moving all the machines from the 3rd region to the 1st region, which taes shiftingCost(=3) dollars, the new machineCount = [20, 10, 20, 20]. Total cost required for these operations = 3.
Use the 1st, 3rd, and 4th regions as the required regions, leaving behind the second region. The total cost = 5 + 3 = 8.

int getMinimumCost(const vector<int>& machineCount, const vector<int>& finalMachineCount, int shiftingCost) {
    vector<int> curr_state(3, 0);

    // Define the recursive function within getMinimumCost
    function<int(int, vector<int>&, int)> solve = [&](int curr_idx, vector<int>& curr_state, int curr_cost) -> int {
        int n = machineCount.size();

        if (curr_idx == n) {
            int TotalCost = curr_cost;
            for (int k = 0; k < 3; ++k) {
                TotalCost += abs(curr_state[k] - finalMachineCount[k]);
            }
            return TotalCost;
        }

        int TotalCost = INT_MAX;
        TotalCost = min(TotalCost, solve(curr_idx + 1, curr_state, curr_cost));

        for (int j = 0; j < 3; ++j) {
            curr_state[j] += machineCount[curr_idx];
            TotalCost = min(TotalCost, solve(curr_idx + 1, curr_state, curr_cost + ((curr_state[j] - machineCount[curr_idx] != 0) ? shiftingCost : 0)));
            curr_state[j] -= machineCount[curr_idx];
        }

        return TotalCost;
    };

    return solve(0, curr_state, 0);
}

---