Fencing an Orchard Plot

Medium

An orchard is an infinite grid: at every point with integer coordinates (i, j) stands an apple tree bearing |i| + |j| apples. You fence off a square plot with sides parallel to the axes, centered at (0, 0). Every tree inside the plot or on its border is yours. Return the smallest perimeter of such a plot that holds at least apples apples.

Example 1

apples=12 → 8

The plot from -1 to 1 on both axes: 4 edge trees with 1 apple and 4 corner trees with 2, for 12 in total. Side 2, perimeter 8.

Example 2

apples=61 → 24

A plot with side 4 gives 60 apples, one short, so the side must be 6 and the perimeter 24.

Example 3

apples=1 → 8

Constraints

1 ≤ apples ≤ 10¹⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Math Binary Search

Similar problems

Digit of Endless Counting Medium Two Squares Make It Medium Growing Steps on a Line Medium N-th Number Divisible by One of Three Medium Prices That Fade With Each Sale Medium

Input

apples=12

Expected

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