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 where0 <= i < n
.abs(nums[i] - nums[i+1]) <= 1
where0 <= i < n-1
.- The sum of all the elements of
nums
does not exceedmaxSum
. 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: The arrays [1,1,2,1] and [1,2,2,1] satisfy all the conditions. There are no other valid arrays with a larger value at the given index.
Example 2:
Input: n = 6, index = 1, maxSum = 10 Output: 3
Constraints:
1 <= n <= maxSum <= 109
0 <= index < n
Solution: Binary Search
To maximize nums[index], we can construct an array like this:
[1, 1, 1, …, 1, 2, 3, …, k – 1, k, k – 1, …,3, 2, 1, …., 1, 1, 1]
Time complexity: O(logn)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua class Solution { public: int maxValue(int n, int index, int maxSum) { int l = 1; int r = maxSum + 1; while (l < r) { int64_t m = l + (r - l) / 2; int64_t t1 = m - index; int64_t t2 = m - (n - 1 - index); int64_t s1 = (t1 + m) * (index + 1) / 2; int64_t s2 = (m + t2) * (n - index) / 2; if (t1 <= 0) s1 = (1 + m) * m / 2 + (index - m + 1); if (t2 <= 0) s2 = (1 + m) * m / 2 + (n - index - m); if (s1 + s2 - m > maxSum) r = m; else l = m + 1; } return l - 1; } }; |