Maximum Value at a Given Index in a Bounded Array | MUST DO | NUMBER THEORY | OA | HARD

https://leetcode.com/problems/maximum-value-at-a-given-index-in-a-bounded-array/

You are given three positive integers: n, index, and maxSum. You want to construct an array nums (0-indexed) that satisfies the following conditions:

1) nums.length == n
2) nums[i] is a positive integer where 0 <= i < n.
3) abs(nums[i] - nums[i+1]) <= 1 where 0 <= i < n-1.
4) The sum of all the elements of nums does not exceed maxSum.
5) nums[index] is maximized.

Return nums[index] of the constructed array.

Note that abs(x) equals x if x >= 0, and -x otherwise.


Example 1:
Input: n = 4, index = 2,  maxSum = 6
Output: 2
Explanation: nums = [1,2,2,1] is one array that satisfies all the conditions.
There are no arrays that satisfy all the conditions and have nums[2] == 3, so 2 is the maximum nums[2].

Example 2:
Input: n = 6, index = 1,  maxSum = 10
Output: 3


Constraints:
1 <= n <= maxSum <= 10^9
0 <= index < n



------------------------------------------------------------------------------------------------------------------------------------

class Solution {
public:
    long long sumRange(long long x, long long y){
        long long SUM_xy=y*(y+1)/2;
        long long SUM_x=(x-1)*x/2;
        return SUM_xy-SUM_x;
    }

    bool isOK(long long val, int n, int index, int sum){

        long long leftSum=sumRange(max(1LL,val-index),val-1);
        if(val-index<1){
            int x=abs(val-index)+1;
            leftSum+=x;
        }

        long long rightSum=sumRange(max(1LL,val-(n-1-index)),val-1);
        if(val-(n-1-index)<1){
            long long x=abs(val-(n-1-index))+1;
            rightSum+=x;
        }

        return leftSum+val+rightSum<=sum;
    }

    int maxValue(int n, int index, int maxSum) {
        int res=0;
        long long low=1;
        long long high=maxSum;
        while(low<=high){
            long long mid=(low+high)/2;
            if(isOK(mid,n,index,maxSum)==true){
                res=mid;
                low=mid+1;
            }
            else{
                high=mid-1;
            }
        }
        return res;
    }
};




IDEA IS THIS, IF I PLACE ANY NUMBER X AT INDEX Y, THEN THE LEFT SIDE WILL CONTAIN Y-1,Y-2,Y-3,1..... AND SO WILL THE RIGHT SIDE, WE CANNOT USE 0, SO AS SOON AS WE HIT 1 WE NEED TO USE IT CONTINUOSLY TO FILL THE REST OF THE SPACES. AND FINALLY CHECK IF THE TOTAL SUM IS LESS OR GREAT THAN MAXSUM

TO FIND THE SUM OF ELEMENTS IN RANGE X TO Y IS SIMPLE.
FIND SUM FROM 1 TO Y. AND THEN SUBTRACT SUM FROM 1 TO X-1, GIVING YOU SUM FROM X TO Y