Minimum Garden Perimeter to Collect Enough Apples
MedPrompt
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:
xifx >= 0-xifx < 0
Example 1:
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: 16Example 3:
Input: neededApples = 1000000000
Output: 5040
Constraints:
1 <= neededApples <= 1015
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Start a loop with
k = 1, where2krepresents 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 ofLto 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 is8 * k. Return this value and terminate. - If not, increment
kand continue to the next iteration.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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
neededAppleswere significantly larger, as the number of iterations is proportional to the cube root ofneededApples.
Solutions
Solution
class Solution { public long minimumPerimeter ( long neededApples ) { long x = 1 ; while ( 2 * x * ( x + 1 ) * ( 2 * x + 1 ) < neededApples ) { ++ x ; } return 8 * x ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.