1295. Minimum Garden Perimeter To Collect Enough Apples¶

LeetCode Problem View on GitHub

1295. Minimum Garden Perimeter to Collect Enough Apples

Medium

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:

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

Solution¶

class Solution {
    public long minimumPerimeter(long neededApples) {
        long low = 1;
        long high = (int)(1e5);
        long ans = -1;
        while (low <= high) {
            long mid = low + (high - low) / 2;
            if (ok(mid, neededApples)) {
                ans = mid;
                high = mid - 1;
            }
            else low = mid + 1;
        }
        System.out.println(ans);
        return ans * 8;
    }

    private static boolean ok(long mid, long need) {
       long total = 2L * mid * (2L * mid * mid + 3L * mid + 1);
       return total >= need;
    }
}

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here