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.

 

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 <= 109
  • 0 <= index < n

Rust Solution

struct Solution;

impl Solution {
    fn max_value(n: i32, index: i32, max_sum: i32) -> i32 {
        let mut l = 1i64;
        let mut r = max_sum as i64;
        let n = n as usize;
        let index = index as usize;
        let mut res = 0;
        let kl = index as i64;
        let kr = (n - index - 1) as i64;
        while l <= r {
            let m = (l + (r - l) / 2) as i64;
            let sum = helper(m, kl) + m + helper(m, kr);
            if sum > max_sum as i64 {
                r = m - 1;
            } else {
                res = res.max(m);
                l = m + 1;
            }
        }
        res as i32
    }
}

fn helper(m: i64, k: i64) -> i64 {
    if m > k {
        (m - 1 + m - 1 - k + 1) * k / 2
    } else {
        (m - 1 + 1) * (m - 1) / 2 + (k - m + 1)
    }
}

#[test]
fn test() {
    let n = 4;
    let index = 2;
    let max_sum = 6;
    let res = 2;
    assert_eq!(Solution::max_value(n, index, max_sum), res);
    let n = 6;
    let index = 1;
    let max_sum = 10;
    let res = 3;
    assert_eq!(Solution::max_value(n, index, max_sum), res);
}

Having problems with this solution? Click here to submit an issue on github.