Show problems as
Classic problem #1802MediumMathBinary SearchGreedy

Maximum Value at a Given Index in a Bounded Array

Real-world version: The Tallest Post at a Chosen Place
Tracked in this browser only
Read Maximum Value at a Given Index in a Bounded Array on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstBitonic Array Search · Binary Search, animated step by step

A fence has n posts in a row, numbered from 0. Every post's height is a whole number of at least 1, posts standing next to each other differ in height by at most 1, and all the heights added together come to at most budget.

Return the greatest height the post at spot can be given.

Examples

Example 1

Input
n = 4, spot = 2, budget = 6
Output
2

Four posts and a budget of six. Making the third post two tall needs heights of one, one, two and one, which adds to five and fits. Making it three tall would need one, two, three and two, adding to eight.

Example 2

Input
n = 6, spot = 1, budget = 10
Output
3

Six posts and a budget of ten. Heights of two, three, two, one, one and one add to exactly ten. Pushing the second post to four would need three either side and cost fourteen.

Example 3

Input
n = 2, spot = 0, budget = 2
Output
1

Two posts and a budget of two leaves nothing over: both posts stand at the minimum of one.

Constraints

  • 1 <= n <= 10^9
  • 1 <= budget <= 10^9
  • n <= budget
  • 0 <= spot <= n - 1

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_value(n: int, spot: int, budget: int) -> int:
Java
public int maxValue(int n, int spot, int budget)

More on the same topics