Minimum Time To Solve The Problems

Hard
0/120
Average time to solve is 50m
profile
Contributed by
13 upvotes
Asked in companies
QuikrBarclaysSprinklr

Problem statement

There are 'N' number of subjects and the ith subject contains subject[i] number of problems. Each problem takes 1 unit of time to be solved. Also, you have 'K' friends, and you want to assign the subjects to each friend such that each subject is assigned to exactly one friend. Also, the assignment of subjects should be contiguous. Your task is to calculate the maximum number of problems allocated to a friend is minimum. See example for more understanding.

For Example: 
If N = 4, K = 2 and subjects = {50,100,300,400}
Assignment of problems can be done in the following ways among the two friends.
{} and {50,100,300,400}. Time required = max(0, 50+100+300+400) = max(0, 850) = 850
{50} and {100,300,400}. Time required = max(50, 100+300+400) = max(50, 800) = 800
{50, 100} and {300,400}. Time required = max(50+100, 300+400) = max(150, 700) = 700
{50,100,300} and {400}. Time required = max(50+100+300, 400) = max(450, 400) = 400
{50,100,300, 400} and {}. Time required = max(50+100+300+400, 0) = max(850, 0) = 850

So, out of all the above following ways, 400 is the lowest possible time.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains a single integer 'T', representing the number of test cases or queries to be run.

Then the 'T' test cases follow. 

The first line of each test case contains a single space-separated two integers 'N' and 'K' representing the total subjects and friends.

The second line of each test case contains 'N' space-separated integers representing the problems of the array “subjects”.
Output format: 
For each test case, print the minimum possible time to solve all the problems.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10 
1 <= N, K <= 10^4
1 <= subjects[i] <= 10^9   

Time limit: 1 sec
Sample Input 1:
1
3 1
20 12 40
Sample Output 1:
72
Explanation for sample 1:
For the first test case, there is only 1 possible way to do the assignment, i.e. {20, 12, 40}. So, the minimum time required is 20 + 12 + 40 = 72.
Sample Input 2:
2
4 8
30 50 40 100
4 2
12 20 50 60
Sample Output 2:
100
82
Explanation for sample 2:
For the first test case, there are 8 friends, but only 4 subjects. So each subject is assigned to one friend and the maximum time taken is max(30, 50, 40, 100) = 100.

For the second test case, the assignment of problems can be done in the following ways.
{} and {12,20,50,60}. Time required = max(0, 12+20+50+60) = max(0, 142) = 142
{12} and {20,50,60}. Time required = max(12, 20+50+60) = max(12, 130) = 130
{12, 20} and {50,60}. Time required = max(12+20, 50+60) = max(32, 110) = 110
{12,20,50} and {60}. Time required = max(12+20+50, 60) = max(82, 60) = 82
{12,20,50, 60} and {}. Time required = max(12+20+50+60, 0) = max(142, 0) = 142
So, out of all the above following ways, 82 is the lowest possible time. Hence, our answer is 82.
Hint

Think of a brute force solution by considering all possible assignments and calculate the result for each assignment.

Approaches (4)
Brute Force

We want to assign N number of subjects among K friends. So consider this as dividing the array into K partitions, where each partition denotes the subjects assigned to one of the friends. Assume that we already have K-1 partitions i.e. we have already assigned the subjects to K-1 friends, and now we want to do the K th partition. So, this last divider can be put between i th and i+1 th subject for 1<=i<=N-1. Note that, putting the divider before the first element is identical to putting it after the last element.

So, after the K th partition, the total time can be calculated as the maximum of below conditions:

  1. The maximum time required among the already existing K-1 partitions.
  2. The time required for the last partition i.e. sum of the array from subjects[i] to subjects[N-1] where the last divider is put before the index i.

Steps:

  1. If the value of K is 1, then we simply return the sum of the array subjects.
  2. If the value of N is 1, then we return subjects[0].
  3. We create an ans variable and initialize it to 10^18 (Any value which is greater than the sum of the array).
  4. Then, run a loop from 1 to N. Let’s denote the loop counter as i.
  5. So, the total time required for this assignment can be calculated as the maximum of the below mentioned conditions:
    1. The time required for the last partition, i.e. K th partition is done after the last element. So, the time required is the sum of elements from i th element to the end of the array, where the k-1 th divider is before element i.
    2. The maximum time required for any partition that is already formed to the left of the k-1 th divider.
  6. If the value calculated in the previous step is less than the ans, then update the ans to this variable.
  7. Finally, return the ans variable.
Time Complexity

O((N^2)^K), where N is the number of subjects and K is the number of friends.

 

In the worst case, for each element in the array “subjects”, we will have K partitions i.e K choices, and also calculate the sum of the array takes O(N) time. Hence, the time complexity becomes O((N^2)^K).

Space Complexity

O(K), where K is the number of friends.

 

In the worst case, extra space is required for the recursive stack. Hence, the space complexity becomes O(K).

Code Solution
(100% EXP penalty)
Minimum Time To Solve The Problems
Full screen
Console