What is the primary pattern used to solve 'Minimum Garden Perimeter to Collect Enough Apples'?

The main pattern is binary search over the valid answer space to find the minimum side length for the square garden.

How do you calculate the number of apples inside a square garden?

The number of apples inside a square garden is derived from a formula based on the sum of absolute values of the coordinates within the square.

What is the time complexity of solving the 'Minimum Garden Perimeter to Collect Enough Apples' problem?

The time complexity is O(log(N)), where N is the upper bound of possible side lengths of the square.

What happens if the side length of the square is too small to contain enough apples?

If the side length is too small, you adjust the binary search bounds to search for larger side lengths until the square contains enough apples.

Can this problem be solved without binary search?

While possible, it would be inefficient. Binary search significantly reduces the number of checks needed, making it the optimal approach.

#1954

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

收集足够苹果的最小花园周长

给你一个用无限二维网格表示的花园，每一个整数坐标处都有一棵苹果树。整数坐标 (i, j) 处的苹果树有 |i| + |j| 个苹果。你将会买下正中心坐标是 (0, 0) 的一块正方形土地，且每条边都与两条坐标轴之一平行。给你一个整数 neededApples ，请你返回土地的最小周长 …

数学二分查找

题目描述

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

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

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

|x| 的值定义为：

如果 x >= 0 ，那么值为 x
如果 x < 0 ，那么值为 -x

示例 1：

输入：neededApples = 1
输出：8
解释：边长长度为 1 的正方形不包含任何苹果。
但是边长为 2 的正方形包含 12 个苹果（如上图所示）。
周长为 2 * 4 = 8 。

示例 2：

输入：neededApples = 13
输出：16

示例 3：

输入：neededApples = 1000000000
输出：5040

提示：

1 <= neededApples <= 10¹⁵

lightbulb

解题思路

方法一：数学 + 枚举

假设正方形右上角坐标为 $(n, n)$ ，那么它的边长为 $2n$ ，周长为 $8n$ ，里面的苹果总数为：

\begin{aligned} &\sum_{x=-n}^{n} \sum_{y=-n}^{n} |x| + |y| \\ \end{aligned}

由于 $x$ 和 $y$ 是对称的，所以可以化简为：

\begin{aligned} &\sum_{x=-n}^{n} \sum_{y=-n}^{n} |x| + |y| \\ &= 2 \sum_{x=-n}^{n} \sum_{y=-n}^{n} |x| \\ &= 2 \sum_{x=-n}^{n} (2n + 1) |x| \\ &= 2 (2n + 1) \sum_{x=-n}^{n} |x| \\ &= 2n(n+1)(2n+1) \end{aligned}

所以，我们只需要枚举 $n$ ，直到找到第一个满足 $2n(n+1)(2n+1) \geq neededApples$ 的 $n$ 即可。

时间复杂度 $O(m^{\frac{1}{3}})$ ，其中 $m$ 为 $neededApples$ 的值。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

class Solution:
    def minimumPerimeter(self, neededApples: int) -> int:
        x = 1
        while 2 * x * (x + 1) * (2 * x + 1) < neededApples:
            x += 1
        return x * 8

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate uses binary search effectively to minimize the number of checks needed to find the valid side length.
question_mark
Candidate understands how to compute the apples inside the square using a formula.
question_mark
Candidate knows how to calculate the perimeter after determining the side length of the square.

warning

常见陷阱

外企场景

error
Candidate fails to correctly derive or use the formula for the number of apples inside a square.
error
Candidate misuses binary search bounds, either searching too broadly or too narrowly.
error
Candidate fails to properly compute the perimeter once the side length is determined.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Add additional constraints on the grid size or allowed range for neededApples.
arrow_right_alt
Allow for different shapes of land (rectangular instead of square) and adjust the perimeter calculation.
arrow_right_alt
Use this problem as a stepping stone to more complex grid-based problems involving multiple plots or obstacles.

help

常见问题

外企场景

继续练习

#1862 向下取整数对和 #1802 有界数组中指定下标处的最大值 #1739 放置盒子