347. Tallest Tower Under Budget
A city planner designs a row of n towers numbered from 0. Every tower must have a height that is a positive whole number, and two neighbouring towers may differ in height by at most 1. The sum of all heights cannot exceed the budget maxSum.
The planner wants the tower at position index to be as tall as possible. Return that maximum height. Trying every height with an O(n) check is too slow when many heights are possible, so look at how the minimum total cost behaves as the height at index grows.
Example 1
- Input:
- n = 5, index = 0, maxSum = 10
- Output:
- 3
- Explanation:
With the first tower at height 3 the row 3, 2, 1, 1, 1 costs 8. Height 4 would need 4, 3, 2, 1, 1 which costs 11 and is over budget, so the answer is 3.
Example 2
- Input:
- n = 3, index = 1, maxSum = 3
- Output:
- 1
- Explanation:
Every tower needs at least 1, which costs exactly 3, so the middle tower cannot rise above 1.
Constraints
1 ≤ n ≤ 105
0 ≤ index < n
n ≤ maxSum ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(log maxSum)
- Space
- O(1)