Description#
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 (i, j)
has |i| + |j|
apples growing on it.
You will buy an axis-aligned square plot of land that is centered at (0, 0)
.
Given an integer neededApples
, return the minimum perimeter of a plot such that at least neededApples
apples are inside or on the perimeter of that plot.
The value of |x|
is defined as:
Example 1:
![](https://spcdn.pages.dev/leetcode/problems/1954.Minimum%20Garden%20Perimeter%20to%20Collect%20Enough%20Apples/images/1527_example_1_2.png)
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.
Example 2:
Input: neededApples = 13
Output: 16
Example 3:
Input: neededApples = 1000000000
Output: 5040
Constraints:
1 <= neededApples <= 1015
Solutions#
Solution 1#
1
2
3
4
5
6
| class Solution:
def minimumPerimeter(self, neededApples: int) -> int:
x = 1
while 2 * x * (x + 1) * (2 * x + 1) < neededApples:
x += 1
return x * 8
|
1
2
3
4
5
6
7
8
9
| class Solution {
public long minimumPerimeter(long neededApples) {
long x = 1;
while (2 * x * (x + 1) * (2 * x + 1) < neededApples) {
++x;
}
return 8 * x;
}
}
|
1
2
3
4
5
6
7
8
9
10
| class Solution {
public:
long long minimumPerimeter(long long neededApples) {
long long x = 1;
while (2 * x * (x + 1) * (2 * x + 1) < neededApples) {
++x;
}
return 8 * x;
}
};
|
1
2
3
4
5
6
7
| func minimumPerimeter(neededApples int64) int64 {
var x int64 = 1
for 2*x*(x+1)*(2*x+1) < neededApples {
x++
}
return 8 * x
}
|
1
2
3
4
5
6
7
| function minimumPerimeter(neededApples: number): number {
let x = 1;
while (2 * x * (x + 1) * (2 * x + 1) < neededApples) {
++x;
}
return 8 * x;
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
| class Solution:
def minimumPerimeter(self, neededApples: int) -> int:
l, r = 1, 100000
while l < r:
mid = (l + r) >> 1
if 2 * mid * (mid + 1) * (2 * mid + 1) >= neededApples:
r = mid
else:
l = mid + 1
return l * 8
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public long minimumPerimeter(long neededApples) {
long l = 1, r = 100000;
while (l < r) {
long mid = (l + r) >> 1;
if (2 * mid * (mid + 1) * (2 * mid + 1) >= neededApples) {
r = mid;
} else {
l = mid + 1;
}
}
return l * 8;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
long long minimumPerimeter(long long neededApples) {
long long l = 1, r = 100000;
while (l < r) {
long mid = (l + r) >> 1;
if (2 * mid * (mid + 1) * (2 * mid + 1) >= neededApples) {
r = mid;
} else {
l = mid + 1;
}
}
return l * 8;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
| func minimumPerimeter(neededApples int64) int64 {
var l, r int64 = 1, 100000
for l < r {
mid := (l + r) >> 1
if 2*mid*(mid+1)*(2*mid+1) >= neededApples {
r = mid
} else {
l = mid + 1
}
}
return l * 8
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| function minimumPerimeter(neededApples: number): number {
let l = 1;
let r = 100000;
while (l < r) {
const mid = (l + r) >> 1;
if (2 * mid * (mid + 1) * (2 * mid + 1) >= neededApples) {
r = mid;
} else {
l = mid + 1;
}
}
return 8 * l;
}
|