1802. Maximum Value at a Given Index in a Bounded Array

//Bruteforce - O(Steps OR Result)/ O(1)
class Solution {
    public int maxValue(int n, int index, int maxSum) {
        int res = 1;
        maxSum -= n;
        int left = 0, right = 0;
        int maxLeft = index, maxRight = n - index - 1;

        while(maxSum > 0) {
            res++;
            int leftVal = Math.min(left++, maxLeft);
            int rightVal = Math.min(right++, maxRight);
            maxSum -= (1 + leftVal + rightVal);
        }
        return (maxSum<0) ? res-1 : res;
    }
}


//Optimized - O(N)/O(1)
class Solution {
    public int maxValue(int n, int index, int maxSum) {
        int res = 1;
        maxSum -= n;
        int left = 0, right = 0;
        int maxLeft = index, maxRight = n - index - 1;

        while(maxSum > 0) {
            res++;
            int leftVal = Math.min(left++, maxLeft);
            int rightVal = Math.min(right++, maxRight);
            maxSum -= (1 + leftVal + rightVal);

            if(leftVal == maxLeft && rightVal == maxRight) {
                break;
            }
        }

        if(maxSum > 0){
            res = res + (maxSum/n);
        }

        return (maxSum<0) ? res-1 : res;
    }
}

//Binary Search 

class Solution {
    public int maxValue(int n, int index, int maxSum) {
        //Binary Search code
        if(n == 1) return maxSum;

        int left = 1, right = maxSum;
        while(left < right) {
            int mid = left + (right-left)/2;
            long sum = calculateSumOfArray(mid, index, n);

            if(sum <= maxSum) {
                left = mid+1;
            }
            else {
                right = mid;
            }
        }

        return left-1;
    }

    //Calculate the Sum of array
    private long calculateSumOfArray(int v, int i, int n){
        long sum = 0;
        if(v <= i){
            int a = i+1-v;
            sum+=summation(v-1) + a;
        }
        else {
            int x = v-i;
            sum+= summation(v-1) - summation(x-1);
        }


        if(v <= n-i){
            int b = n-i-v;
            sum+=summation(v-1) + b;
        }
        else {
            int y = v-(n-i-1);
            sum+= summation(v-1) - summation(y-1);
        }

        return sum+v;

    }

    //Utility method to apply summation formula
    private long summation(int n) {
        return (long)(n+1)*n/2;
    }

}