Minimum Time To Solve The Problems
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.

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

Question

Minimum Time To Solve The Problems

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.

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

Accepted Answer

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:

The maximum time required among the already existing K-1 partitions.
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:

If the value of K is 1, then we simply return the sum of the array subjects.
If the value of N is 1, then we return subjects[0].
We create an ans variable and initialize it to 10^18 (Any value which is greater than the sum of the array).
Then, run a loop from 1 to N. Let’s denote the loop counter as i.
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.
If the value calculated in the previous step is less than the ans, then update the ans to this variable.
Finally, return the ans variable.

Space Complexity: O(n)Explanation:

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).

Time Complexity: O(n^n)Explanation:

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).

Accepted Answer

Dp with Memoization

In the previous approach, the algorithm recursively calculates and compares every possible partition at every possible element, which has many overlapping subproblems. i.e. a recursive function computes the same sub-problems again and again. So we can use memoization to overcome the overlapping subproblems. To reiterate, memoization is when we store the results of all previously solved subproblems and return the minimum time required to solve the problems, from the dp[i][j] if we encounter the problem that has already been solved.

Since there are two states those are changing in the recursive function, i.e. N and K, so we use the 2-dimensional array dp[][] to store all the subproblems, where dp[i][j] will store the result from 0 to i th friend and from 0 to j th subject.

Another optimization that can be done is that, like in the previous approach, instead of calculating the sum of the array from subjects[i] to subjects[N-1] again and again, we can create a prefixSum array to store the prefix sum of the array subjects and get the sum from subjects[i] to subjects[N-1] in constant time.

Steps:

Create a prefixSum array of size N.
The steps to calculate the prefix sum:
1. Initialize all the elements of this array to 0.
2. Make the first element of the prefixSum array equal to the first element of subjects.
3. Then run a loop from i = 1 to N and do:
  1. prefixSum[i] = prefixSum[i-1] + subjects[i].
Now, create a dp array of size (K+1 * N+1). Initialize the values in the dp array to -1.
Implement, and call the function minimumRequiredTimeUtil(subjects, N, K, dp, prefixSum).

minimumRequiredTimeUtil(subjects, N, K, dp, prefixSum):

If the value of K is 1, then we simply return prefixSum[N-1].
If the value of N is 1, then we return subjects[0].
If the value in the dp table is not -1, then we simply return that value.
Else, initialize an ans variable to 10^18, and run a loop from i = 1 to N and do:
1. ans = min(ans, max(minimumRequiredTimeUtil(subjects, i, K-1, dp, prefixSum), prefixSum[n-1] - prefixSum[i-1]))
Finally, assign the ans to dp[K][N] and return the ans.

Space Complexity: O(m*n) - For 2d arraysExplanation:

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

In the worst case, extra space is required to create the dp array of size K*N i.e O(K*N) and also for the recursion stack. Hence, the overall complexity will be O(K*N).

Time Complexity: O(n^3)Explanation:

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

In the worst case, for each K partition, we iterate the whole array “subjects” once and in each iteration we put the divider at each index from 0 to the current index of “subjects”. Hence, the time complexity becomes O(K*N^2).

Accepted Answer

Bottom-up DP

The idea is to use a bottom-up dynamic programming approach instead of a memoization approach. Here also, for each partition we have the choices to put the divider between the i th and i+1 th subject for 1 <= i <= N-1. So, with the outer loop running from i = 2 to K and the inner loop running from j = 2 to N, we can use the recurrence relation of memoization approach as dp[i][j] = min(dp[i][j], max(dp[i-1][x], prefixSum[j-1] - prefixSum[x-1])) where 1 <= x <= j.

Steps:

Create a prefixSum array of size N.
The steps to calculate the prefix sum:
1. Initialize all the elements of this array to 0.
2. Make the first element of the prefixSum array equal to the first element of subjects.
3. Then run a loop from i = 1 to N and do:
  1. prefixSum[i] = prefixSum[i-1] + subjects[i].
Create a dp array of size (K+1 * N+1). Initialize the values in the dp array to -1.
If the value of K is 1, then we simply return prefixSum[n-1].
If the value of N is 1, then we return subjects[0].
Run a loop from i = 1 to N and do:
1. dp[1][i] = prefixSum[i-1]
Run another loop from i = 1 to K and do:
1. dp[i][1] = subjects[0]
Run a nested loop with the outer loop running from i = 2 to K and the inner loop running from j = 2 to N and do:
1. Initialize an ans variable to 10^18.
2. Run another loop from x = 1 to j and do:
  1. ans = min(ans, max(dp[i-1][x], prefixSum[j-1] - prefixSum[x-1]))
3. dp[i][j] = ans.
Finally, return dp[K][N].

Space Complexity: O(m*n) - For 2d arraysExplanation:

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

In the worst case, the extra space required to create the dp array is of size K*N. Hence, the overall complexity is O(K*N).

Time Complexity: O(n^3)Explanation:

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

In the worst case, for each K partition, we iterate the whole array “subjects” once and in each iteration we put the partition at each index from 0 to the current index of “subjects”. Hence, the time complexity becomes O(K*N^2).

Accepted Answer

Binary search

The idea here is to perform the binary search. We know that the binary search can be performed if the following conditions hold.

The target value should lie in a particular range.
The search space is sorted.
After each iteration, the search space is reduced to half.

So, in order to perform a binary search, we need to detect a suitable search space first. For that, let’s find out the minimum possible value and the maximum possible value of the answer. We can safely assume the lowest possible value of the answer is 0 when the array is empty. However, the highest possible value occurs when the value of K = 1. In that case, the answer is the sum of all the elements in the array “subjects”. So, the highest possible value is the sum of the array “subjects”. So, the range of the search space is [0, the sum of the array subjects].

Now, let us consider that we have t number of friends, so as the value in the above range decreases, the value of t increases and vice-versa. So, by performing the binary search in the range [0, the sum of the array subjects], for each mid in the range, we check whether it is possible to do K partitions such that the answer is mid. We can do so by implementing another function, say, checker. If it is possible to do K partitions for this value of mid, that means we have enough friends to solve the problems in the given time i.e. mid, so we update the upper bound of the range to mid - 1 storing the answer as mid. If it is not possible to do K partitions, that means we do not have enough friends to solve the problems in the given time, so we update the lower bound of the range to mid+1.

Steps:

Initialize a sum variable to 0 and calculate the sum of the array.
If the value of K is 1, then we simply return the sum.
If the value of N is 1, then we return subjects[0].
Take two pointers left and right with left pointing to 0 and right to the sum. Create an ans variable and initialize it to the sum.
Now apply the binary search in the range from left to right. For this, run a loop while left <= right and do:
1. Create a mid variable and mid = left + (right - left) / 2
2. For each mid value, check whether it is possible to do K partitions with the answer as mid. For doing so, implement a function checker(subjects, N, K, mid).
3. If it is possible to do so, then update right to mid-1 and ans to mid.
4. Else, update left to mid+1.
Finally, return the ans variable.

bool checker(subjects, N, K, mid):

Create a temp variable and initialize it to mid and a count variable to 1.
Initialize a loop counter let’s say i to 0 and run the loop until i < N and do:
1. If at any point count exceeds K, then simply return false. As it is not possible to do K partitions.
2. If ith value of array subjects is greater than temp, then increment count by 1 and make temp equal to mid again.
3. Else, decrement temp by i th value of subjects and increment i by 1.
Finally, return true if we get out of the loop.

Space Complexity: O(1)Explanation:

O(1).

In the worst case, a constant space is required.

Time Complexity: O(nlogn)Explanation:

O(N * log(S)), where N is the number of subjects, and S is the sum of subjects array.

In the worst case, for all the mid values O(log(S), we may have to traverse the whole array “subjects”, which takes O(N) time. Hence, the total time complexity becomes O(N * log(S)).

For Example:

Input format:

Output format:

Note:

Constraints:

Top Google Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern

Top HR questions asked in Google Software Developer Intern