Maximum Value at a Given Index in a Bounded Array

class Solution {
public:
    int maxValue(int n, int index, int maxSum) {
        auto sideSum = [](long long v, long long len) {
            if (v >= len) return (v + v - len + 1) * len / 2; // v, v-1, ..., v-len+1
            return (v + 1) * v / 2 + (len - v);                // v, ..., 1, 1, ..., 1
        };
        auto totalSum = [&](long long v) {
            return v + sideSum(v - 1, index) + sideSum(v - 1, n - 1 - index);
        };
        long long lo = 1, hi = maxSum;
        while (lo < hi) {
            long long mid = lo + (hi - lo + 1) / 2;
            if (totalSum(mid) <= maxSum) lo = mid;
            else hi = mid - 1;
        }
        return (int)lo;
    }
};

func maxValue(n int, index int, maxSum int) int {
    sideSum := func(v, length int64) int64 {
        if v >= length {
            return (v + v - length + 1) * length / 2
        }
        return (v+1)*v/2 + (length - v)
    }
    totalSum := func(v int64) int64 {
        return v + sideSum(v-1, int64(index)) + sideSum(v-1, int64(n-1-index))
    }
    lo, hi := int64(1), int64(maxSum)
    for lo < hi {
        mid := lo + (hi-lo+1)/2
        if totalSum(mid) <= int64(maxSum) {
            lo = mid
        } else {
            hi = mid - 1
        }
    }
    return int(lo)
}

class Solution:
    def maxValue(self, n: int, index: int, maxSum: int) -> int:
        def side_sum(v: int, length: int) -> int:
            if v >= length:
                return (v + v - length + 1) * length // 2
            return (v + 1) * v // 2 + (length - v)

        def total_sum(v: int) -> int:
            return v + side_sum(v - 1, index) + side_sum(v - 1, n - 1 - index)

        lo, hi = 1, maxSum
        while lo < hi:
            mid = lo + (hi - lo + 1) // 2
            if total_sum(mid) <= maxSum:
                lo = mid
            else:
                hi = mid - 1
        return lo

function maxValue(n, index, maxSum) {
    const sideSum = (v, length) => {
        if (v >= length) return (v + v - length + 1n) * length / 2n;
        return (v + 1n) * v / 2n + (length - v);
    };
    const totalSum = (v) => v + sideSum(v - 1n, BigInt(index)) + sideSum(v - 1n, BigInt(n - 1 - index));
    let lo = 1n, hi = BigInt(maxSum);
    const target = BigInt(maxSum);
    while (lo < hi) {
        const mid = lo + (hi - lo + 1n) / 2n;
        if (totalSum(mid) <= target) lo = mid;
        else hi = mid - 1n;
    }
    return Number(lo);
}

class Solution {
    public int maxValue(int n, int index, int maxSum) {
        long lo = 1, hi = maxSum;
        while (lo < hi) {
            long mid = lo + (hi - lo + 1) / 2;
            if (totalSum(mid, index, n) <= maxSum) lo = mid;
            else hi = mid - 1;
        }
        return (int) lo;
    }

    private long sideSum(long v, long len) {
        if (v >= len) return (v + v - len + 1) * len / 2;
        return (v + 1) * v / 2 + (len - v);
    }

    private long totalSum(long v, int index, int n) {
        return v + sideSum(v - 1, index) + sideSum(v - 1, n - 1 - index);
    }
}

function maxValue(n: number, index: number, maxSum: number): number {
    const sideSum = (v: bigint, length: bigint): bigint => {
        if (v >= length) return (v + v - length + 1n) * length / 2n;
        return (v + 1n) * v / 2n + (length - v);
    };
    const totalSum = (v: bigint): bigint =>
        v + sideSum(v - 1n, BigInt(index)) + sideSum(v - 1n, BigInt(n - 1 - index));
    let lo = 1n, hi = BigInt(maxSum);
    const target = BigInt(maxSum);
    while (lo < hi) {
        const mid = lo + (hi - lo + 1n) / 2n;
        if (totalSum(mid) <= target) lo = mid;
        else hi = mid - 1n;
    }
    return Number(lo);
}