1954. Minimum Garden Perimeter to Collect Enough Apples LeetCode Solution

In this guide, you will get 1954. Minimum Garden Perimeter to Collect Enough Apples LeetCode Solution with the best time and space complexity. The solution to Minimum Garden Perimeter to Collect Enough Apples problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum Garden Perimeter to Collect Enough Apples solution in C++
Minimum Garden Perimeter to Collect Enough Apples solution in Java
Minimum Garden Perimeter to Collect Enough Apples solution in Python
Additional Resources

1954. Minimum Garden Perimeter to Collect Enough Apples LeetCode Solution image

Problem Statement of Minimum Garden Perimeter to Collect Enough Apples

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

Complexity Analysis

Time Complexity: O(\log 10^5) = O(1)
Space Complexity: O(1)

1954. Minimum Garden Perimeter to Collect Enough Apples LeetCode Solution in C++

class Solution {
 public:
  long long minimumPerimeter(long long neededApples) {
    long l = 1;
    long r = 100'000;  // \sqrt [3] {10^{15}}

    while (l < r) {
      const long m = (l + r) / 2;
      if (numApples(m) >= neededApples)
        r = m;
      else
        l = m + 1;
    }

    return l * 8;
  }

 private:
  // Returns the number of apples at the k-th level.
  //    k := the level making perimeter = 8k
  // p(k) := the number of apples at the k-th level on the perimeter
  // n(k) := the number of apples at the k-th level not no the perimeter
  //
  // p(1) =             1 + 2
  // p(2) =         3 + 2 + 3 + 4
  // p(3) =     5 + 4 + 3 + 4 + 5 + 6
  // p(4) = 7 + 6 + 5 + 4 + 5 + 6 + 7 + 8
  // p(k) = k + 2(k+1) + 2(k+2) + ... + 2(k+k-1) + 2k
  //      = k + 2k^2 + 2*k(k-1)/2
  //      = k + 2k^2 + k^2 - k = 3k^2
  //
  // n(k) = p(1) + p(2) + p(3) + ... + p(k)
  //      = 3*1  + 3*4  + 3*9  + ... + 3*k^2
  //      = 3 * (1 + 4 + 9 + ... + k^2)
  //      = 3 * k(k+1)(2k+1)/6 = k(k+1)(2k+1)/2
  // So, the number of apples at the k-th level should be
  //   k(k+1)(2k+1)/2 * 4 = 2k(k+1)(2k+1)
  long numApples(long k) {
    return 2 * k * (k + 1) * (2 * k + 1);
  }
};
/* code provided by PROGIEZ */

1954. Minimum Garden Perimeter to Collect Enough Apples LeetCode Solution in Java

class Solution {
  public long minimumPerimeter(long neededApples) {
    long l = 1;
    long r = 100_000; // \sqrt [3] {10^{15}}

    while (l < r) {
      final long m = (l + r) / 2;
      if (numApples(m) >= neededApples)
        r = m;
      else
        l = m + 1;
    }

    return l * 8;
  }

  // Returns the number of apples at the k-th level.
  //    k := the level making perimeter = 8k
  // p(k) := the number of apples at the k-th level on the perimeter
  // n(k) := the number of apples at the k-th level not no the perimeter
  //
  // p(1) =             1 + 2
  // p(2) =         3 + 2 + 3 + 4
  // p(3) =     5 + 4 + 3 + 4 + 5 + 6
  // p(4) = 7 + 6 + 5 + 4 + 5 + 6 + 7 + 8
  // p(k) = k + 2(k+1) + 2(k+2) + ... + 2(k+k-1) + 2k
  //      = k + 2k^2 + 2k(k-1)/2
  //      = k + 2k^2 + k^2 - k = 3k^2
  //
  // n(k) = p(1) + p(2) + p(3) + ... + p(k)
  //      = 31  + 34  + 39  + ... + 3k^2
  //      = 3 * (1 + 4 + 9 + ... + k^2)
  //      = 3 * k(k+1)(2k+1)/6 = k(k+1)(2k+1)/2
  // So, the number of apples at the k-th level should be
  //   k(k+1)(2k+1)/2 * 4 = 2k(k+1)(2k+1)
  private long numApples(long k) {
    return 2L * k * (k + 1) * (2 * k + 1);
  }
}
// code provided by PROGIEZ

1954. Minimum Garden Perimeter to Collect Enough Apples LeetCode Solution in Python

class Solution:
  def minimumPerimeter(self, neededApples: int) -> int:
    def numApples(k: int) -> int:
      """Returns the number of apples at the k-th level.

         k := the level making perimeter = 8k
      p(k) := the number of apples at the k-th level on the perimeter
      n(k) := the number of apples at the k-th level not no the perimeter

      p(1) =             1 + 2
      p(2) =         3 + 2 + 3 + 4
      p(3) =     5 + 4 + 3 + 4 + 5 + 6
      p(4) = 7 + 6 + 5 + 4 + 5 + 6 + 7 + 8
      p(k) = k + 2(k+1) + 2(k+2) + ... + 2(k+k-1) + 2k
          = k + 2k^2 + 2*k(k-1)//2
          = k + 2k^2 + k^2 - k = 3k^2

      n(k) = p(1) + p(2) + p(3) + ... + p(k)
          = 3*1  + 3*4  + 3*9  + ... + 3*k^2
          = 3 * (1 + 4 + 9 + ... + k^2)
          = 3 * k(k+1)(2k+1)//6 = k(k+1)(2k+1)//2
      So, the number of apples at the k-th level should be
        k(k+1)(2k+1)//2 * 4 = 2k(k+1)(2k+1)
      """
      return 2 * k * (k + 1) * (2 * k + 1)

    return bisect.bisect_left(range(100_000), neededApples,
                              key=numApples) * 8
 # code by PROGIEZ