Welcome to Subscribe On Youtube

1954. Minimum Garden Perimeter to Collect Enough Apples

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:

  • 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

Solutions

Solution 1: Direct Implementation

Assume that the coordinates of the upper right corner of the square are $(n, n)$, then its side length is $2n$, its perimeter is $8n$, and the total number of apples inside is:

\[\begin{aligned} &\sum_{x=-n}^{n} \sum_{y=-n}^{n} |x| + |y| \\ \end{aligned}\]

Since $x$ and $y$ are symmetric, they can be simplified to:

\[\begin{aligned} &\sum_{x=-n}^{n} \sum_{y=-n}^{n} |x| + |y| \\ &= 2 \sum_{x=-n}^{n} \sum_{y=-n}^{n} |x| \\ &= 2 \sum_{x=-n}^{n} (2n + 1) |x| \\ &= 2 (2n + 1) \sum_{x=-n}^{n} |x| \\ &= 2n(n+1)(2n+1) \end{aligned}\]

So, we just need to enumerate $n$ until we find the first $n$ that satisfies $2n(n+1)(2n+1) \geq neededApples$.

Time complexity $O(m^{\frac{1}{3}})$, where $m$ is the value of $neededApples$. Space complexity $O(1)$.

Solution 2

We can also enumerate $n$ in two, with time complexity $O(\log m)$.

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


// Solution 2
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;
    }
}


  • 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;
    }
};


// Solution 2
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;
    }
};


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


# Solution 2
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


  • func minimumPerimeter(neededApples int64) int64 {
	var x int64 = 1
	for 2*x*(x+1)*(2*x+1) < neededApples {
		x++
	}
	return 8 * x
}


// Solution 2
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
}


  • function minimumPerimeter(neededApples: number): number {
    let x = 1;
    while (2 * x * (x + 1) * (2 * x + 1) < neededApples) {
        ++x;
    }
    return 8 * x;
}


// Solution 2
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;
}

All Problems

All Solutions