# Minimum Garden Perimeter to Collect Enough Apples
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-garden-perimeter-to-collect-enough-apples)
Canonical: https://scaleengineer.com/dsa/problems/minimum-garden-perimeter-to-collect-enough-apples
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
---
## Problem
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:

* `x` if `x >= 0`
* `-x` if `x < 0`

**Example 1:**

![](https://assets.glich.co/dsa/minimum-garden-perimeter-to-collect-enough-apples/image0.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`

# Approaches
## Linear Search
This is a straightforward brute-force approach. We test values of `k` starting from 1, where `2k` is the side length of the square plot. For each `k`, we calculate the total number of apples within the plot and stop as soon as this number meets or exceeds `neededApples`.
**Time:** O(N^(1/3)), where `N` is `neededApples`. The number of apples `C(k)` grows approximately as `4k^3`. Thus, the value of `k` we are looking for is proportional to the cube root of `N`. The loop runs `k` times. · **Space:** O(1), as we only use a few variables to store the current `k` and apple count.
**Pros:** Simple to understand and implement.; Requires minimal mathematical analysis beyond deriving the apple count formula.
**Cons:** While it passes for the given constraints, it can be inefficient if `neededApples` were significantly larger, as the number of iterations is proportional to the cube root of `neededApples`.
### Explanation
The total number of apples `C(k)` for a square plot extending from `-k` to `k` on both axes is given by the formula `C(k) = 2 * k * (k+1) * (2k+1)`. The algorithm iterates `k` from 1 upwards. In each step, it computes `C(k)` and compares it with `neededApples`. The first `k` for which `C(k) >= neededApples` is the one we need. The perimeter is then `8 * k`. We must use 64-bit integers (`long` in Java) for the apple count to avoid overflow, as `neededApples` can be up to 10^15.

```java
class Solution {
    public long minimumPerimeter(long neededApples) {
        long k = 0;
        while (true) {
            k++;
            // Use long for all parts of the calculation to prevent overflow
            long currentApples = 2 * k * (k + 1) * (2 * k + 1);
            if (currentApples >= neededApples) {
                break;
            }
        }
        return 8 * k;
    }
}
```
### Algorithm
- Start a loop with `k = 1`, where `2k` represents the side length of the square plot.
- In each iteration, calculate the total apples for the square defined by `[-k, k]` on both axes using the formula: `currentApples = 2L * k * (k + 1) * (2L * k + 1)`. Note the use of `L` to ensure calculations are done using 64-bit longs to prevent overflow.
- Check if `currentApples >= neededApples`.
- If the condition is met, we have found the smallest `k`. The perimeter is `8 * k`. Return this value and terminate.
- If not, increment `k` and continue to the next iteration.

## Binary Search
The number of apples, `C(k) = 2k(k+1)(2k+1)`, is a monotonically increasing function of `k`. This property allows us to use binary search to find the smallest `k` that satisfies `C(k) >= neededApples` much more efficiently than a linear search.
**Time:** O(log U), where `U` is the upper bound of the search space for `k`. This is extremely fast. · **Space:** O(1), as it only requires a few variables for the search bounds and answer.
**Pros:** Significantly faster than linear search, with logarithmic time complexity.; Guaranteed to find the solution quickly and is a robust method for monotonic functions.
**Cons:** Slightly more complex to implement than a simple loop.; Requires choosing a safe upper bound for the search space, which might need some preliminary analysis.
### Explanation
Instead of checking every `k` from 1, binary search intelligently narrows down the possibilities. We define a search space for `k` and repeatedly divide it in half. For each midpoint `mid`, we calculate the apple count `C(mid)`. If `C(mid)` is sufficient, we know `mid` is a possible answer, and we try to find an even smaller `k` that also works by searching in the lower half of the range. If `C(mid)` is insufficient, we know `mid` and all smaller values are not the answer, so we must search for a larger `k` in the upper half. This process quickly converges to the smallest `k` that satisfies the condition.

```java
class Solution {
    public long minimumPerimeter(long neededApples) {
        long low = 1, high = 100000; // A safe upper bound for k
        long ans = high;
        while (low <= high) {
            long mid = low + (high - low) / 2;
            long currentApples = 2 * mid * (mid + 1) * (2 * mid + 1);
            
            if (currentApples >= neededApples) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans * 8;
    }
}
```
### Algorithm
- Establish a search range for `k`. The lower bound `low` can be `1`. The upper bound `high` can be a safe, sufficiently large number like `100000` (since `k` for `10^15` apples is ~63000).
- Initialize a variable `ans` to hold the result.
- Loop while `low <= high`:
  - Calculate the midpoint `mid = low + (high - low) / 2`.
  - Compute the number of apples for `k = mid`: `apples = 2L * mid * (mid + 1) * (2L * mid + 1)`.
  - If `apples >= neededApples`, it means `mid` is a possible answer. We store it (`ans = mid`) and try to find a smaller `k` by searching in the left half (`high = mid - 1`).
  - If `apples < neededApples`, `mid` is too small. We must search for a larger `k` in the right half (`low = mid + 1`).
- After the loop terminates, `ans` holds the smallest `k` found. Return the perimeter `8 * ans`.

## Mathematical Approximation
This is the most efficient approach, leveraging a mathematical approximation to find the required value of `k` almost directly. This nearly eliminates the need for a search, resulting in a constant-time solution.
**Time:** O(1). The `cbrt` function is a constant time operation, and the subsequent loop runs for a small, constant number of iterations because the initial guess is very accurate. · **Space:** O(1).
**Pros:** The fastest possible approach with O(1) time complexity.; Demonstrates a deep understanding of the problem's mathematical properties.
**Cons:** Relies on floating-point arithmetic (`cbrt`), which can have precision issues if not handled carefully.; The implementation can be slightly more complex than binary search if aiming for perfect robustness against edge cases.
### Explanation
The formula for the number of apples, `C(k) = 2k(k+1)(2k+1)`, is dominated by the `k^3` term for large values of `k`. We can approximate `C(k)` as `4k^3`. By setting `4k^3 ≈ neededApples`, we can solve for `k` to get an excellent estimate: `k ≈ (neededApples / 4)^(1/3)`. We can compute this value using a cube root function (`Math.cbrt` in Java). The true integer solution will be extremely close to this floating-point estimate. A simple search starting from the floor of this estimate will find the correct `k` in just a few iterations (usually 1 or 2). This makes the overall time complexity effectively constant.

```java
class Solution {
    public long minimumPerimeter(long neededApples) {
        // Start with a guess based on the approximation 4k^3 ≈ neededApples.
        // Subtract a small constant to be safe from floating point and approximation errors.
        long k = (long) Math.cbrt(neededApples / 4.0) - 2;
        if (k < 1) {
            k = 1;
        }

        // This loop will start very close to the answer and run only a few times.
        while (2 * k * (k + 1) * (2 * k + 1) < neededApples) {
            k++;
        }
        
        return 8 * k;
    }
}
```
### Algorithm
- We need to find the smallest integer `k` such that `2k(k+1)(2k+1) >= neededApples`.
- Approximate the formula `2k(k+1)(2k+1)` as `4k^3` for large `k`.
- Solve the approximation for `k`: `4k^3 ≈ neededApples` => `k ≈ (neededApples / 4)^(1/3)`.
- Calculate an initial guess for `k` using the cube root function: `k_guess = (long) Math.cbrt(neededApples / 4.0)`.
- The actual integer `k` will be very close to `k_guess`. Start a search from `k_guess` (or a slightly smaller value like `k_guess - 2` to be safe) and increment until the exact formula `2k(k+1)(2k+1) >= neededApples` is satisfied.
- The number of checks required will be very small, making the search part negligible.

# Solutions
### Java

```java
class Solution { public long minimumPerimeter ( long neededApples ) { long x = 1 ; while ( 2 * x * ( x + 1 ) * ( 2 * x + 1 ) < neededApples ) { ++ x ; } return 8 * x ; } }
```

### CPP

```cpp
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 ; } };
```

### Python

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