1802. 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:

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

Return nums[index] of the constructed array.

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

class Solution {
    long extraSpaceSize(long space) {
        return space >= 0 ? space : (-space + 1) * space / 2;
    }
public:
    int maxValue(int n, int index, int maxSum) {
        long l(0), r(INT_MAX), m, res(1);
        while(l <= r) {
            m = (l + r)>>1;

            if(m * m + extraSpaceSize(index + 1 - m) + extraSpaceSize(n - index - m) <= maxSum) {
                res = max(res, m);
                l = m + 1;
            } else {
                r = m - 1;
            }
        }

        return res;
    }
};