1954

1954. 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

Companies:
Amazon

Related Topics:
Math, Binary Search

Solution 1.

// OJ: https://leetcode.com/problems/minimum-garden-perimeter-to-collect-enough-apples/
// Author: github.com/lzl124631x
// Time: O(root(T, 3))
// Space: O(1)
class Solution {
public:
    long long minimumPerimeter(long long target) {
        long long sum = 0, f = 0, i = 1;
        for (; true; ++i) {
            f += i * (i + 1) * 3 / 2;
            sum = f * 8 - 6 * i * (i + 1);
            if (sum >= target) return 8 * i;
        }
    }
};

Solution 2. Math

// OJ: https://leetcode.com/problems/minimum-garden-perimeter-to-collect-enough-apples/
// Author: github.com/lzl124631x
// Time: O(root(T, 3))
// Space: O(1)
class Solution {
public:
    long long minimumPerimeter(long long target) {
        for (long long i = 1; true; ++i) {
            if (i * (i + 1) * (2 * i + 1) * 2 >= target) return 8 * i;
        }
    }
};