Code

Python

def getMinServers(expected_load, servers):
    # Initialize DP array, large value to represent impossible state    dp = [float('inf')] * (expected_load + 1)
    dp[0] = 0  # Base case: 0 load requires 0 servers    # For each server, update the dp array    for server in servers:
        for load in range(expected_load, server - 1, -1):
            dp[load] = min(dp[load], dp[load - server] + 1)
    # If dp[expected_load] is still infinity, it means we cannot serve the load    return dp[expected_load] if dp[expected_load] != float('inf') else -1

C++

#include <iostream>#include <vector>#include <algorithm>#include <climits>using namespace std;// TODO:// 1. Initialize a dynamic programming (dp) array where dp[i] represents the minimum number of servers//    required to handle exactly i requests. Set dp[0] = 0 (0 servers are needed to handle 0 requests),//    and initialize all other entries as infinity.// 2. For each server capacity, update the dp array by considering whether adding that server can//    reduce the number of servers needed to achieve a specific load.// 3. Traverse the dp array from expected_load down to the server's capacity to ensure no overwriting of results.// 4. After processing all servers, check dp[expected_load].//    - If it is still infinity, return -1 (no valid combination of servers can handle the exact load).//    - Otherwise, return dp[expected_load] which contains the minimum number of servers needed.int getMinServers(int expected_load, const vector<int>& servers) {    // Step 1: Initialize dp array with "infinity" values    vector<int> dp(expected_load + 1, INT_MAX);    dp[0] = 0;  // 0 servers are needed to achieve a load of 0    // Step 2: Process each server capacity    for (int server : servers) {        // Traverse from the right (expected_load) to prevent overwriting in the same iteration        for (int load = expected_load; load >= server; --load) {            if (dp[load - server] != INT_MAX) {                dp[load] = min(dp[load], dp[load - server] + 1);            }        }    }    // Step 3: Check if the expected load can be achieved    return dp[expected_load] == INT_MAX ? -1 : dp[expected_load];}

Explanation of the Code:

1. getMinServers() Function:
   • Initialization: We create a dp array where each element is initialized to INT_MAX (representing infinity) except for dp[0] = 0 (no servers are needed to achieve a load of 0).
   • Dynamic Programming Transition: For each server capacity, we iterate backward from expected_load to the server’s capacity to avoid overwriting results from the same iteration. If adding the current server reduces the number of servers needed to achieve a certain load, we update the dp array accordingly.
   • Final Check: After processing all servers, we check the value of dp[expected_load]. If it’s still INT_MAX, it means it’s impossible to achieve the exact load, and we return 1. Otherwise, dp[expected_load] contains the minimum number of servers required.