We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Garden Perimeter to Collect Enough Apples

Number: 1295

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

In an infinite 2D grid, every integer coordinate has an apple tree that produces |i| + |j| apples at position (i, j). You want to buy an axis-aligned square plot of land centered at (0, 0) that collects at least a given number of apples (the sum from all trees inside or on the perimeter of the square). The task is to find the minimum perimeter of such a square plot.

Key Insights

  • The plot is a square centered at (0, 0) with corners at (k, k), (k, -k), (-k, k), and (-k, -k) where k is the half-side length.
  • A tree at coordinate (i, j) provides |i| + |j| apples.
  • Due to symmetry, the sum of apples in the square with |i|, |j| ≤ k can be computed efficiently using a derived formula.
  • The total number is given by: S(k) = 2 * (2k + 1) * k * (k + 1).
  • Since S(k) is monotonically increasing with k, binary search can be used to find the smallest k such that S(k) is at least neededApples.

Space and Time Complexity

Time Complexity: O(log X), where X is the value of k that meets the condition.
Space Complexity: O(1)

Solution

We first derive that the sum of apples, S, in the square plot with half-length k is:

S(k) = 2 * (2k + 1) * k * (k + 1)

This formula comes from summing |i| and |j| over all points in the square and using symmetry. Our goal is to find the smallest integer k for which S(k) ≥ neededApples, and then the perimeter of the square plot is 8 * k (since each side is of length 2k).

The solution uses a binary search:

  1. Set initial boundaries: left = 0 and right as an upper bound (found by doubling until S(right) is at least neededApples).
  2. Compute mid = (left + right) / 2.
  3. If S(mid) is greater than or equal to neededApples, store mid as a candidate and search for a smaller k (set right = mid – 1).
  4. Otherwise, continue the search with left = mid + 1.
  5. Finally, output the perimeter which is 8 * k.

This approach efficiently finds the minimal k needed and, consequently, the minimal perimeter.

Code Solutions

# Function to compute the total number of apples in the square of half-length k.
def total_apples(k):
    # S(k) = 2 * (2k + 1) * k * (k + 1)
    return 2 * (2 * k + 1) * k * (k + 1)

def minPerimeter(neededApples: int) -> int:
    # Initialize binary search boundaries.
    left, right = 0, 1
    # Increase right until we have an upper bound where total_apples(right) >= neededApples.
    while total_apples(right) < neededApples:
        right *= 2
        
    # Perform binary search to find the smallest k meeting the condition.
    result = right
    while left <= right:
        mid = (left + right) // 2
        if total_apples(mid) >= neededApples:
            result = mid  # Candidate found, try to find a smaller one.
            right = mid - 1
        else:
            left = mid + 1
    
    # The perimeter of the square is 8 * k.
    return result * 8

# Example usage:
# print(minPerimeter(1))           # Expected output: 8
# print(minPerimeter(13))          # Expected output: 16
# print(minPerimeter(1000000000))  # Expected output: 5040
← Back to All Questions