Minimum garden perimeter to collect enough apples

Math Binary Search

55.5% acceptance

Feb 25, 2026

407

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

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_perimeter(needed_apples: i64) -> i64 {
    // For a square plot with half-side length n, the total apples = 2*n*(n+1)*(2*n+1)
    let mut lo: i64 = 1;
    let mut hi: i64 = 100000; // enough for 10^15
    while lo < hi {
      let mid = lo + (hi - lo) / 2;
      let apples = 2 * mid * (mid + 1) * (2 * mid + 1);
      if apples >= needed_apples {
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    8 * lo
  }
}