Today I have done leetcode's June LeetCoding Challenge with cpp.

June LeetCoding Challenge 10

Description

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

Solution

int64_t S(int64_t h, int64_t l) {
  return (2 * h - l + 1) * l / 2;
}

int FindExtra(int start, int increment, int maxSum) {
  int64_t b = start * 2 / increment - 1;
  int64_t c = 2 * maxSum / increment;

  int64_t d = sqrt(b * b + 4 * c);
  int n = (d - b) / 2;
  return n;
}

class Solution {
public:
  int maxValue(int n, int index, int maxSum) {
    maxSum -= n;
    int left = index + 1;
    int right = n - index;
    auto [small, large] = minmax(left, right);

    int64_t A = S(large, large) + S(large, small) - large;
    if(maxSum >= A) {
      return large + (maxSum - A) / n + 1;
    }
    int64_t B = S(small, small) * 2 - small;
    if(maxSum >= B) {
      return small + FindExtra(small * 2, 1, maxSum - B) + 1;
    }
    return FindExtra(1, 2, maxSum) + 1;
  }
};

// Accepted
// 370/370 cases passed (4 ms)
// Your runtime beats 42.79 % of cpp submissions
// Your memory usage beats 46.27 % of cpp submissions (6 MB)