# 1954. Minimum Garden Perimeter to Collect Enough Apples
###### tags: `Leetcode` `Medium` `Math`
Link: https://leetcode.com/problems/minimum-garden-perimeter-to-collect-enough-apples/description/
## 思路
### 方法一 $O(\sqrt{n})$

layer 1: 4*1+4*2 = 4*3
layer 2: 4*2+8*3+4*4 = 4*12
layer 3: 4*3+8*4+8*5+4*6 = 4*27

观察发现假设边长每次增加2是一个新的layer
那么layer ```i```的苹果数就是

### 方法二 $O(logX^{\frac{1}{3}})$
X is the range of input
参考[这里](https://leetcode.com/problems/minimum-garden-perimeter-to-collect-enough-apples/solutions/1375478/java-c-python-binary-search-and-o-1-soluitons/?orderBy=most_votes)
假设顶点是(r,r),(r,-r),(-r,r) and (-r,-r)
我们把apples分成4块 每块都是一个长方形 每块的size都是```r*(r+1)```
![](https://i.imgur.com/yvEsX3D.png)
把两个蓝框叠在一起
把每个位置的apple相加
那每个位置的apple数就是```r+r+1```
一个蓝框里面的apple总数就是 ```r*(r+1)*(r+r+1)```

同理一个绿框里面的apple总数就是```r*(r+1)*(r+r+1)```

因此整个图的apple数就是```r*r*r*4+r*r*6+r*2```

接着用binary search找答案即可
## Code
### 方法一

class Solution:
def minimumPerimeter(self, neededApples: int) -> int:
curr = 0
i = 1
while curr<neededApples:
curr += 4*i+4*2*i
curr += 8*(i+1+2*i-1)*(i-1)//2
i += 1
return 8*(i-1)

### 方法二

class Solution:
def minimumPerimeter(self, neededApples: int) -> int:
start, end = 1, 1000000
while start<end:
mid = start+(end-start)//2
tmp = pow(mid, 3)*4+pow(mid, 2)*6+mid*2
if tmp<neededApples:
start = mid+1
else: end = mid
return 8*start