Covid Vaccination

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, ... , 1, 2, 3, ... , peak]
   here leftSum = no of ones - 1 + (peak * (peak+1))/2
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.

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.

The steps are as follows:

• 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.
• Initialize two variables ‘start’ and ‘end’ to 1 and maxVaccines, respectively, denoting the first and last index of the array.
• We run a while loop with a condition start is less than or equal to the end:
  • We will initialize a variable ‘mid ’equal to (end-start)/2 + start.
  • 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 will check if the value of x is equal to ‘maxVaccines’; this is the most optimal condition. So, we will return mid as the final answer.
• If the value of x is smaller than ‘maxVaccines,’ then we will search for the second half of the array, i.e., we will update the value of start to mid + 1.
• If the value of x is greater than or equal to ‘maxVaccines,’ then we will search for the first half of the array, i.e., we will update the value of end to mid - 1.
• When we come out of the loop, then we will return ‘end’ as the final answer as this was most optimal condition in the while loop.