---
# System prepended metadata

title: 1954. Minimum Garden Perimeter to Collect Enough Apples
tags: [Leetcode, Medium, Math]

---

# 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```的苹果数就是
```4*i+8*sum of all nums between in [i+1, 2*i-1]+4*2*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
### 方法一
```python=
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)
```
### 方法二
```python=
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
```