minimum-garden-perimeter-to-collect-enough-apples

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

In a garden represented as an infinite 2D grid, there is an apple tree planted at every integer coordinate. The apple tree planted at an integer coordinate <code>(i, j)</code> has <code>|i| + |j|</code> apples growing on it.

You will buy an axis-aligned square plot of land that is centered at <code>(0, 0)</code>.

Given an integer <code>neededApples</code>, return the minimum perimeter of a plot such that at least <code>neededApples</code> apples are inside or on the perimeter of that plot.

The value of <code>|x|</code> is defined as:

<ul>
	<li><code>x</code> if <code>x &gt;= 0</code></li>
	<li><code>-x</code> if <code>x &lt; 0</code></li>
</ul>

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2019/08/30/1527_example_1_2.png" style="width: 442px; height: 449px;" />
<pre>
Input: neededApples = 1
Output: 8
Explanation: A square plot of side length 1 does not contain any apples.
However, a square plot of side length 2 has 12 apples inside (as depicted in the image above).
The perimeter is 2 * 4 = 8.
</pre>

Example 2:

<pre>
Input: neededApples = 13
Output: 16
</pre>

Example 3:

<pre>
Input: neededApples = 1000000000
Output: 5040
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= neededApples &lt;= 1015</code></li>
</ul>

minimumPerimeter

Minimum Garden Perimeter to Collect Enough Apples

Math

Binary Search

给你一个用无限二维网格表示的花园，每一个&nbsp;整数坐标处都有一棵苹果树。整数坐标&nbsp;<code>(i, j)</code>&nbsp;处的苹果树有 <code>|i| + |j|</code>&nbsp;个苹果。

你将会买下正中心坐标是 <code>(0, 0)</code>&nbsp;的一块 正方形土地&nbsp;，且每条边都与两条坐标轴之一平行。

给你一个整数&nbsp;<code>neededApples</code>&nbsp;，请你返回土地的&nbsp;最小周长&nbsp;，使得&nbsp;至少&nbsp;有&nbsp;<code>neededApples</code>&nbsp;个苹果在土地&nbsp;里面或者边缘上。

<code>|x|</code>&nbsp;的值定义为：

<ul>
	<li>如果&nbsp;<code>x &gt;= 0</code>&nbsp;，那么值为&nbsp;<code>x</code></li>
	<li>如果&nbsp;<code>x &lt;&nbsp;0</code>&nbsp;，那么值为&nbsp;<code>-x</code></li>
</ul>

&nbsp;

示例 1：
<img alt="" src="https://pic.leetcode-cn.com/1627790803-qcBKFw-image.png" style="width: 442px; height: 449px;" />
<pre>
输入：neededApples = 1
输出：8
解释：边长长度为 1 的正方形不包含任何苹果。
但是边长为 2 的正方形包含 12 个苹果（如上图所示）。
周长为 2 * 4 = 8 。
</pre>

示例 2：

<pre>
输入：neededApples = 13
输出：16
</pre>

示例 3：

<pre>
输入：neededApples = 1000000000
输出：5040
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= neededApples &lt;= 1015</code></li>
</ul>