Server Manager

Moderate
0/80
profile
Contributed by
3 upvotes
Asked in companies
Urban Company (UrbanClap)Google inc

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
4
7 3 9 12
7
1 2 3 4 5 6 7
Sample Output 1 :
1
0
Explanation For Sample Input 1 :
In the first test case, we can divide the load between two servers like - {7, 9} and {3, 12}. Hence the absolute load difference is 1.

In the second test case, There can be many possible ways to divide the load:
{1,3,4,6} and {2,5,7}
{1,2,5,6} and {3,4,7}
{1,2,4,7} and {3,5,6}
{1,6,7} and {2,3,4,5}
All of them result in the minimum possible load of 0.
Sample Input 2 :
2
3
9 49 39
4
1 2 3 4
Sample Output 2 :
1
0
Hint

Check for every possible subsequence and calculate the minimum possible difference.

Approaches (4)
Brute Force

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”.
Time Complexity

O( N * 2 ^ N ), where N is the size of the array “loads”.

 

As we are Iterating through 0 to N for every element of the loop from 0 to 2^N.

Hence the time complexity is O( N * 2 ^ N ).

Space Complexity

O( 1 )

 

No extra space is used.

Hence the space complexity is O(1).

Code Solution
(100% EXP penalty)
Server Manager
Full screen
Console