Last Updated: 3 Sep, 2021
Server Manager
Moderate
Asked in companies
Sheldon is working for coding ninjas as server manager. Due to excessive traffic on the website, he is asked to reduce the load by dividing the total traffic into two servers. He is given an array of integers “load” denoting the load by every process, He wants to divide the load into two parts such that the absolute difference between both the servers is minimum. As Sheldon is too busy with his other chores. Help him to find the minimum possible absolute difference.
For Example :
load = {10, 11, 7, 5}
In the given example, the total load can be divided such that the first server handles processes 1st and 3rd and the second server handles processes 2nd and 4th. Hence the absolute difference is abs((10 + 7) - (11 + 5)) = 1.
So the final answer is 1.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:
The first line of each test case contains a single integer ‘N’ denoting the total number of processes.
The next N lines each contain “load[i]” denoting the load by each process.
Output Format :
For each test case, print a single integer “ans” denoting the minimum absolute difference of the total load on the two servers.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 10
1 <= N <= 100
1 <= load[i] <= 50
Time limit: 1 sec
Approaches
In this approach, we will check for every possible subsequence which can be formed by the list of loads and take an integer “answer” in which we will store the minimum possible load and return the “answer” after checking every possible subsequence.
The steps are as follows:
- Take an integer “sum” in which we will store the sum of all the elements of the array “loads”.
- Iterate through the array “loads” from 0 to n-1(say iterator be i):
- Update “sum” = “sum” + “loads[i]”.
- Now take an Integer “answer” in which we will store the minimum possible difference which is possible for the given array.
- Iterate from 0 to 2 ^ n(say iterator be i):
- Take an integer “process” in which we will store the processes of the current subsequence.
- Iterate through the loop from 0 to n(say iterator be j):
- If the value of (2 ^ i & j) != 0 add “loads[j]” to “process”.
- Update “answer” = min(abs(“sum” - “process” - “process”), “answer”).
- Return “answer”.
In this approach, we will call a recursive function for an index and we will generate two cases:
- Include the current processes in the first server.
- Include the current processes in the second server.
And return the minimum possible difference from the recursion.
The steps are as follows:
- In the “main” function:
- Take an integer “sum” in which we will store the total number of processes.
- Iterate through the array from 0 to n-1 and update the value of “sum” = “sum” + “loads[i]”.
- Take an integer “server1” and initialize it by 0, in which we will store the total number of processes we are giving to the 1st server.
- Call the function “recursion” and pass the array “loads”, the current index(starting from N), and “sum” and “server1”.
- In the “recursion” function:
- Take a base case, i.e. if the index is 0 return abs("sum” - “server1” - “server1”).
- Take an integer “answer”.
- Update “answer” with the minimum of the two cases:
- If we include the current processes in server1, “answer” = recursion(“loads”, “index” - 1, “server1” + “loads[i-1]”, “sum”).
- Else if we do not include the current processes in server1, “answer” = recursion(“loads”, “index” - 1, “server1”, “sum”).
- Return “answer”.
This approach is similar to the previous approach, the only difference is we are storing the minimum cost for all subarrays and use the precomputed values when required.
The steps are as follows:
- In the “main” function:
- Take an integer “sum” in which we will store the total number of processes.
- Iterate through the array from 0 to n-1 and update the value of “sum” = “sum” + “loads[i]”.
- Define a 2D vector “dp” in which we will store the minimum absolute difference after including the current index for any value which is less than the “sum”.
- Take an integer “server1” and initialize it by 0, in which we will store the total number of processes we are giving to the 1st server.
- Call the function “recursion” and pass the array “loads”, the current index(starting from N), “server1”, and “sum” and “dp”.
- In the “recursion” function:
- Take a base case, i.e. if the index is 0 return abs("sum” - “server1” - “server1”).
- Take a pointer to integer “answer” = dp[index][server1].
- If answer already has some value, it means we have already computed this index for the current sum, return “answer”
- Else Update “answer” with the minimum of the two cases:
- If we include the current processes in server1, “answer” = recursion(“loads”, “index” - 1, “server1” + “loads[i-1]”, “sum”, dp).
- Else if we do not include the current processes in server1, “answer” = recursion(“loads”, “index” - 1, “server1”, “sum”, dp).
- Return “answer”.
In this approach we will take a 2D array “dp”. “dp[i][j]” will store whether it is possible to have the total number of processes ‘j’ in 1st server, taking the “ith” process.
The steps are as follows:
- Take two 2D arrays “dp” and initialize the dp array by 0 and an integer “sum” in which we will store the sum of all the processes.
- Iterate through the array “loads” from 0 to n-1(say iterator be i):
- Update “sum” = “sum” + “loads[i]”.
- Iterate through the array from 0 to n-1(say iterator be i):
- Update dp[i][0] = 1.
- Take a loop from 1 to sum(say iterator be j):
- Update dp[i][j] = dp[i][j-1].
- Now if j - loads[i] >= 0:
- Update the value of “dp[i][j]” |= “dp[i - 1][j - “loads[i]”]”.
- Iterate through a for loop from sum/2 to 0(say iterator be i):
- Return “sum” - 2 * ‘i’ if for the current value of ‘i’, “dp[n - 1][i]” = 1.
Similar problems