Maximum Value at Index K

1. The sum of all elements of the array should not be more than ‘L’. 2. The absolute difference between any adjacent pair of indices in the array should not be more than 1. 3. The value at the K'th index of the array should be maximized.

The first line of the input contains an integer, 'T,’ denoting the number of test cases. The first line of each test case contain three space-separated integers, 'N', 'L', and ‘K’, denoting the number of elements in the array, the maximum sum of the constructed array, and the index whose value needs to be maximized respectively.

1 <= T <= 10 1 <= N <= 10^5 1 <= L <= 10^9 0 <= K < N Where 'T' denotes the number of test cases, 'N' denotes the number of elements in the array, 'L' denotes the maximum sum of the constructed array, and 'K’ denotes the index whose value needs to be maximized. Time limit: 1 sec

For the first test case, An array of positive integers having size 3 and sum less than or equal to 7 with the value of index 1 maximized is [2,3,2]. Hence, the answer is 3 in this case. For the second test case, The possible arrays of positive integers having size 3 and sum less than or equal to 5 with the value of index 0 maximized are [2,1,2], [2,2,1] and [2,1,1]. Hence, the answer is 2 in this case.

Brute force

Our approach is to try to place every value between 1 to L at the K'th index and check if an array can be constructed or not. We will try to find the array having a minimum sum generated by placing the value at the K'th index and comparing the sum of the array with L.

For a particular value val at K'th index, the array having minimum sum will have the below form:

[..,max(1,val-2), max(1,val-1), val, max(1,val-1), max(1,val-2),..]

We want all elements of the array to have the minimum value possible to obtain a minimal sum. To get the minimum sum, we are trying to decrease val by 1 at every step as the difference between any adjacent pair of indices can not exceed 1. Once val is reduced to 1, then all the remaining indexes will be assigned 1 because we are trying to construct an array with positive integers.

Algorithm:

We will initialize the variable maxValue with 0, and it will store the maximum possible value at the K'th index of the constructed array.
Iterate val from 1 to L,
- We will set the variable minSum as val. The variable minSum stores the minimum sum that could be generated by placing the value val at the K’th index.
- Iterate pos from K-1 to 0 and find the minimum value that could be placed at pos that is the difference of val and distance between K and pos index. Add the minimum value to minSum. Note that the minimum value that could be placed at the index of the array is 1.
- Iterate pos from K+1 to N-1 and update minSum by adding the minimum value to minSum that could be placed at index pos. Note that the minimum value that could be placed at the index of the array is 1.
- If minSum is less than or equal to L, then update maxValue with val.
Return the variable maxValue.

Time Complexity

O(N*L), where N is the number of elements in the array and L is the maximum sum of the constructed array.

We are doing L iterations and in each iteration, it takes O(N) time to find the minimum sum of the optimal array that could be generated. .Hence the overall time complexity is O(N*L).

Space Complexity

O(1).

Constant space is being used. Hence, the overall Space Complexity is O(1).

Problem statement

Sample Input 1 :

Sample Output 1 :

Explanation of sample input 1 :

Sample Input 2 :

Sample Output 2 :