Covid Vaccination
We are suffering from the Second wave of Covid-19. The Government is trying to increase its vaccination drives. Ninja wants to help the Government to plan an effective method to help increase vaccination following safety measures. Time is running out. Can you help the nation?

You are given two positive integers: ‘n,’ ‘maxVaccines’ denoting the number of days for which this vaccination drive will go on and the total number of vaccines available for the drive, respectively. You have to find the number of vaccines administered each day. You are also given a number ‘dayNumber,’ and we are interested to know the maximum number of vaccines that can be administered on ‘dayNumber’ th day.

The rules of the vaccination drive :

1. There should be a positive number of vaccines administered each day during the vaccination drive.

2. The absolute difference between the number of vaccines in two consecutive days should not exceed 1.

3. The sum of all the elements of the vaccines array does not exceed maxVaccines, that is, you cannot administer more vaccines than what is provided to you.

4. Vaccines administered on ‘dayNumber’ th day should be maximized.

Input Format:

The first line of input contains an integer ‘T,’ denoting the number of test cases. The test cases follow. The first line contains three space-separated integers ‘n’, ‘dayNumber,’ and ‘maxVaccines,’ denoting the number of days for which this vaccination drive will go on, the total number of vaccines available for the campaign, and the day for which the number of vaccines administered needs to be maximized respectively.

Output Format:

For each test case, print an integer denoting the maximum number of vaccines administered on the day ‘dayNumber’. Print the output of each test case in a separate line.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints:

1

Question

Covid Vaccination

We are suffering from the Second wave of Covid-19. The Government is trying to increase its vaccination drives. Ninja wants to help the Government to plan an effective method to help increase vaccination following safety measures. Time is running out. Can you help the nation?

You are given two positive integers: ‘n,’ ‘maxVaccines’ denoting the number of days for which this vaccination drive will go on and the total number of vaccines available for the drive, respectively. You have to find the number of vaccines administered each day. You are also given a number ‘dayNumber,’ and we are interested to know the maximum number of vaccines that can be administered on ‘dayNumber’ th day.

The rules of the vaccination drive :

1. There should be a positive number of vaccines administered each day during the vaccination drive.

2. The absolute difference between the number of vaccines in two consecutive days should not exceed 1.

3. The sum of all the elements of the vaccines array does not exceed maxVaccines, that is, you cannot administer more vaccines than what is provided to you.

4. Vaccines administered on ‘dayNumber’ th day should be maximized.

Input Format:

The first line of input contains an integer ‘T,’ denoting the number of test cases. The test cases follow.

The first line contains three space-separated integers ‘n’, ‘dayNumber,’ and ‘maxVaccines,’ denoting the number of days for which this vaccination drive will go on, the total number of vaccines available for the campaign, and the day for which the number of vaccines administered needs to be maximized respectively.

Output Format:

For each test case, print an integer denoting the maximum number of vaccines administered on the day ‘dayNumber’.

Print the output of each test case in a separate line.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints:

1<= T <= 50
1 <= n <=  maxVaccines <= 10^9
0 <= dayNumber < n


Time Limit: 1 sec

Accepted Answer

Brute force

The idea is to choose a peak value at the ‘dayNumber’ th index. Then we can create the array like a mountain with the peak of the mountain being at the ‘dayNumber’ th index. The sum of the elements of this array must be less than or equal to maxVaccines.If we find that the sum is greater, then we have chosen a high peak value, and if it is less, then it means we have chosen a smaller peak value. So we have to select the peak value such that given conditions are fulfilled. So we can iterate from maxVaacines to 1 and check if this is the peak value for which the array can be created. If we find such a peak, then we will return its value.

We need to find the maximum number, which can be the peak of the array vaccine,s and the sum of the array will not exceed maxVaccines.

Let the peak of the array or vaccines[dayNumber] be x.

Then, we can say the array may look like [... x-2 x-1 x x-1 x-2 …] since abs([vaccine[i+1] - vaccine[i]) <= 1. However, while making the array, we will not decrease after reaching 1 since vaccines[i] > 0.

We can easily find the formula for the total sum of the array vaccines from the peak value and we do not need to create the whole array.

Let's take the left part of the peak as an example. It can have 2 cases:

[1,1,1, ... , 1, 2, 3, ... , peak]
here leftSum = no of ones - 1 + (peak * (peak+1))/2
[k, k+1, k+2, ... , peak-1, peak]
How to calculate this? This subarray can be regarded as a portion of the following array: [{1, 2, 3, ... , k-1} + {k, k+1, ... , peak}]. So it's easy to get the equation as leftSum = (peak * (peak + 1)) / 2 - (k * (k + 1)) / 2

The same thing goes with the right side.

If the number of elements of the array on the left side of the peak is less than the peak value, we will get situation 2, and if it is more or equal, then we get situation 1. Now we can use the formula according to the situation and find the sum of elements on the left of the peak. Similarly, we can find the sum of the elements to the right of the peak. So we get the sum of all the elements of the array. Now we see if this sum is equal to, less than, or greater than maxVaccines.

If it is equal or less, then this is the required peak value. If it is more, we have to reduce the peak value till we get the desired value.

Now, we need to iterate from maxCapacity till we find an x that satisfies the sum (vaccines) <= maxVaccines. We will stop iterating when we find such a value, and that will be our answer.

The steps are as follows:

We will initialize two variables ‘left’ and ‘right’ to dayNumber and n-1-dayNumber, respectively, denoting left of peak array elements number and right of peak array elements number respectively.
We will initialize a variable ans with 1 denoting the value at the required index.
- We will iterate from i = 0 to maxVaccines - 1:
  - We will declare a function solve which takes 3 arguments mid, left, right denoting the mid value, number of elements to the left of the peak, number of elements to the right of the peak. It returns the sum of the elements of the array.
  - Solve function returns the sum of elements of the array.
    - We will initialize a variable sum with mid*mid.
    - If (mid - 1) is greater than equal to the left sum, then decrement sum by k*(k+1)/2 where k equals mid - 1- left.
    - Else increment sum by the value left - mid +1.
    - If (mid - 1) is greater than equal to the right sum, then decrement sum by k*(k+1)/2 where k equals mid - 1- right.
    - Else increment sum by right - mid +1.
    - We will return the value of the sum as the final answer.
We initialize x with the value returned by recursive function solve, which has 3 parameters(i, left, right), denoting the value of i the number of elements to the left of mid and the number of elements to the right of mid.
If x less than equals ‘maxSum’, we set ans = i and break out of the loop.
We will return ‘ans’ as the final answer.

Space Complexity: O(1)Explanation:

O(1)

As we are not using any extra space. Hence, the overall space complexity is O(1).

Time Complexity: O(n)Explanation:

O(maxVaccines), where maxVaccines is the total number of vaccines available for the drive.

As we check for all values from maxVaccines to 1, there are at most ‘maxVaccines’ number of iterations. Hence the overall complexity is O(maxVaccines).

Python (3.5)

'''

	Time Complexity: O(maxVaccines)

	Space Complexity: O(1)



	Where 'maxVaccines' denotes the number of days of the Vaccination drive.

'''





def solve(mid, left, right):



    sum = mid * mid



    if (mid - 1 >= left):



        # Finding sum if the number of elements to the left of peak is less than the peak value

        k = mid - 1 - left

        sum -= k * (k + 1) // 2



    else:

        # Finding sum if the number of elements to the left of peak is more than the peak value

        sum += left - mid + 1



    if (mid - 1 >= right):



        # Finding sum if the number of elements to the right of peak is less than the peak value

        k = mid - 1 - right

        sum -= k * (k + 1) // 2



    else:

        #Finding sum if the number of elements to the right of peak is more than the peak value

        sum += right - mid + 1



    # Return sum of elements of the array

    return sum





def maxVaccinesAdministered(n, dayNumber, maxVaccines):



    # Finding out the number of elements to the left and right of the peak

    left = dayNumber

    right = n - 1 - dayNumber



    # Initialising the start and the end value

    start = 1

    end = maxVaccines



    ans = 0



    # Iterating over the peak values

    for i in range(maxVaccines, 0, -1):

        if (solve(i, left, right) <= maxVaccines):



            # Modifying answer if condition is satisfied

            ans = i

            break



    # Returning the maximum value possible at the given index

    return ans

Java (SE 1.8)

/*
	Time Complexity: O(maxVaccines)
	Space Complexity: O(1)

	Where 'maxVaccines' denotes the number of days of the Vaccination drive.
*/

public class Solution {

	public static int solve(int mid, int left, int right){
		int sum = mid * mid;
		if (mid - 1 >= left) {

			// Finding sum if the number of elements to the left of peak is less than the peak value
		    int k = mid - 1 - left;
		    sum -= k * (k + 1) / 2;

		} else {

		    // Finding sum if the number of elements to the left of peak is more than the peak value
			sum += left - mid + 1;

		}
		if (mid - 1 >= right) {

			// Finding sum if the number of elements to the right of peak is less than the peak value
		    int k = mid - 1 - right;
		    sum -= k * (k + 1) / 2;

		} else {

		    // Finding sum if the number of elements to the right of peak is more than the peak value
		    sum += right - mid + 1;
		}

		// Return sum of elements of the array
		return sum;
	}

    public static int maxVaccinesAdministered(int n, int dayNumber, int maxVaccines) {
    	
    	// Finding out the number of elements to the left and right of the peak
		int left = dayNumber;
		int right = n - 1 - dayNumber;

		// Initializing start and end value
		int start = 1;
		int end = maxVaccines;

		int ans = 0;

		// Iterating over the peak values
		for (int i = maxVaccines; i >= 1; i--) {
		    if (solve(i, left, right) <= maxVaccines) {

		      // Modifying ans if condition is satisfied
		      ans = i;
		      break;
		    }

		}

		// Returning the maximum value possible at the given index
		return ans;
    }
}

C++ (g++ 5.4)

/*

	Time Complexity: O(maxVaccines)

	Space Complexity: O(1)



	Where 'maxVaccines' denotes the number of days of the Vaccination drive.

*/



int solve(int mid, int left, int right) {

  int sum = mid * mid;

  if (mid - 1 >= left) {



    // Finding sum if the number of elements to the left of peak is less than the peak value

    int k = mid - 1 - left;

    sum -= k * (k + 1) / 2;



  } else {



    // Finding sum if the number of elements to the left of peak is more than the peak value

    sum += left - mid + 1;



  }

  if (mid - 1 >= right) {



    // Finding sum if the number of elements to the right of peak is less than the peak value

    int k = mid - 1 - right;

    sum -= k * (k + 1) / 2;



  } else {



    // Finding sum if the number of elements to the right of peak is more than the peak value

    sum += right - mid + 1;

  }



  // Return sum of elements of the array

  return sum;

}



int maxVaccinesAdministered(int n, int dayNumber, int maxVaccines) {



  // Finding out the number of elements to the left and right of the peak

  int left = dayNumber;

  int right = n - 1 - dayNumber;



  // Initializing start and end value

  int start = 1;

  int end = maxVaccines;



  int ans = 0;



  // Iterating over the peak values

  for (int i = maxVaccines; i >= 1; i--) {

    if (solve(i, left, right) <= maxVaccines) {



      // Modifying ans if condition is satisfied

      ans = i;

      break;

    }



  }



  // Returning the maximum value possible at the given index

  return ans;

}

Accepted Answer

Binary Search

In the previous approach, we were iterating from maxVaccines to 1 to find the peak value for which the sum of vaccines array does not exceed maxVaccines. Here to choose the peak value, we are using binary search.

In binary search, we divide the interval in which the value we are searching for lies into two halves.

Here we set start = 1 , end = maxVaccines and mid = start + (end - start) / 2

We assign the mid value to the peak, and using this value, we calculate the total number of vaccines administered.

If the sum of the vaccine array satisfies the given conditions for mid as the peak value, then there is a possibility that a higher value of peak might also fulfill the requirement.

So, we change left to mid + 1

However, if mid does not satisfy the conditions, it is obvious the value of peak has to be smaller, and we set right to mid - 1.

The above process is repeated till the start becomes greater than the end, and the maximum value of the peak that satisfies the given conditions is our answer.