Tallest Peak on a Budget

Medium

You need to build an array of length positive integers (indexed from zero) such that: - neighbouring elements differ by at most 1; - the sum of all elements does not exceed budget. Among all such arrays, make the element at position spot as large as possible and return that value.

Example 1

length=5, spot=1, budget=9 → 3

For instance, [2, 3, 2, 1, 1]: the sum is 9 and neighbours differ by at most 1. A 4 at position 1 is impossible, since it needs at least 3 + 4 + 3 + 2 + 1 = 13.

Example 2

length=3, spot=2, budget=3 → 1

The budget only covers an array of all ones.

Example 3

length=4, spot=0, budget=20 → 6

Constraints

1 ≤ length ≤ budget ≤ 10⁹
0 ≤ spot < length

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Binary Search

Similar problems

Stick Triples That Form a Triangle Medium Best-Paid Gig for Each Worker Medium A Note From Headline Cutouts Medium A Plan for Draining Ponds Medium Prices That Fade With Each Sale Medium

Input

length=5, spot=1, budget=9

Expected

Run checks the first 3 tests in your browser. Submit checks all 75 tests on the server, hidden ones included.