Minimum Garden Perimeter to Collect Enough Apples

Minimum Garden Perimeter to Collect Enough Apples - Problem

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

Input & Output

Example 1 — Small Square

$ Input: neededApples = 1

› Output: 8

💡 Note: The smallest square that contains at least 1 apple has radius 1. At radius 1, we have a 3×3 grid with total 12 apples, which is ≥ 1. Perimeter = 8 × 1 = 8.

Example 2 — Medium Square

$ Input: neededApples = 13

› Output: 16

💡 Note: At radius 1: 12 apples (not enough). At radius 2: 60 apples (≥ 13). So minimum radius is 2, perimeter = 8 × 2 = 16.

Example 3 — Larger Square

$ Input: neededApples = 1000000000

› Output: 5040

💡 Note: For very large needed apples, we use binary search to find the minimum radius efficiently. The answer is perimeter = 8 × 630 = 5040.

Constraints

1 ≤ neededApples ≤ 2 × 10¹⁵

Visualization

Tap to expand

Understanding the Visualization

Input

neededApples = 13

Process

Find minimum square radius containing ≥13 apples

Output

Return perimeter = 8 × radius

Key Takeaway

🎯 Key Insight: Use mathematical formula with binary search to efficiently find minimum square radius

Asked in

G Google 15 a Amazon 12 M Microsoft 8 A Apple 6

The key insight is recognizing that apple distribution forms diamond patterns based on Manhattan distance |i|+|j|. Use the mathematical formula 2×n×(n+1)×(2n+1) for total apples in radius n, combined with binary search to find minimum radius efficiently. Best approach is Binary Search with Mathematical Formula. Time: O(log(√neededApples)), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Answer	O(log(√neededApples))	O(1)	Binary search on the radius to find minimum perimeter efficiently
Brute Force - Linear Search	O(√neededApples)	O(1)	Expand square radius one by one until we have enough apples
Mathematical Formula	O(log(√neededApples))	O(1)	Derive and use closed-form mathematical formula to calculate apple count

Binary Search on Answer — Algorithm Steps

Set search bounds: left=0, right=large value
For middle radius, calculate total apples using formula
If apples >= needed, try smaller radius (right = mid)
If apples < needed, try larger radius (left = mid + 1)
Return perimeter when bounds converge

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Bounds

Set left=0, right=100000

Check Middle

Calculate apples for mid radius

Adjust Bounds

Narrow search based on result

Code -

solution.c — C

#include <stdio.h>

long long solution(long long neededApples) {
    long long left = 0, right = 100000;
    
    while (left < right) {
        long long mid = left + (right - left) / 2;
        // Total apples in square with radius mid: 2*mid*(mid+1)*(2*mid+1)
        long long totalApples = 2LL * mid * (mid + 1) * (2 * mid + 1);
        
        if (totalApples >= neededApples) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return 8 * left; // Perimeter is 8*radius
}

int main() {
    long long neededApples;
    scanf("%lld", &neededApples);
    long long result = solution(neededApples);
    printf("%lld\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log(√neededApples))

Binary search on radius values, which are proportional to square root of needed apples

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra variables for binary search bounds

✓ Linear Space

23.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Answer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler