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 theminimum perimeter of a plot such that at least****neededApples apples areinside or on the perimeter of that plot.

The value of |x| is defined as:

  • x if x >= 0
  • -x if x < 0

Examples

Example 1

1
2
3
4
5
6
7
8


![](https://assets.leetcode.com/uploads/2019/08/30/1527_example_1_2.png)

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

1
2

Input: neededApples = 13
Output: 16

Example 3

1
2

Input: neededApples = 1000000000
Output: 5040

Constraints

  • 1 <= neededApples <= 1015

Solution

Method 1 – Binary Search on Perimeter

Intuition

The apples in the garden are distributed such that the number of apples inside a square of side 2k (centered at (0,0)) can be calculated with a formula. We can use binary search to find the minimum k such that the total apples is at least neededApples.

Approach

  1. For a given k, calculate the total apples inside the square using the formula: total = 2 * k * (k + 1) * (2 * k + 1).
  2. Use binary search to find the smallest k such that total >= neededApples.
  3. The perimeter is 8 * k.
  4. Return the perimeter.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    long long apples(long long k) {
        return 2 * k * (k + 1) * (2 * k + 1);
    }
    long long minimumPerimeter(long long neededApples) {
        long long l = 1, r = 1e6, ans = 0;
        while (l <= r) {
            long long m = l + (r - l) / 2;
            if (apples(m) >= neededApples) {
                ans = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return 8 * ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func minimumPerimeter(neededApples int64) int64 {
    apples := func(k int64) int64 {
        return 2 * k * (k + 1) * (2*k + 1)
    }
    l, r := int64(1), int64(1e6)
    var ans int64
    for l <= r {
        m := l + (r-l)/2
        if apples(m) >= neededApples {
            ans = m
            r = m - 1
        } else {
            l = m + 1
        }
    }
    return 8 * ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public long minimumPerimeter(long neededApples) {
        long l = 1, r = (long)1e6, ans = 0;
        while (l <= r) {
            long m = l + (r - l) / 2;
            long total = 2 * m * (m + 1) * (2 * m + 1);
            if (total >= neededApples) {
                ans = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return 8 * ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun minimumPerimeter(neededApples: Long): Long {
        var l = 1L
        var r = 1_000_000L
        var ans = 0L
        fun apples(k: Long) = 2 * k * (k + 1) * (2 * k + 1)
        while (l <= r) {
            val m = l + (r - l) / 2
            if (apples(m) >= neededApples) {
                ans = m
                r = m - 1
            } else {
                l = m + 1
            }
        }
        return 8 * ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def minimum_perimeter(needed_apples: int) -> int:
    def apples(k: int) -> int:
        return 2 * k * (k + 1) * (2 * k + 1)
    l, r, ans = 1, int(1e6), 0
    while l <= r:
        m = l + (r - l) // 2
        if apples(m) >= needed_apples:
            ans = m
            r = m - 1
        else:
            l = m + 1
    return 8 * ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn minimum_perimeter(needed_apples: i64) -> i64 {
        fn apples(k: i64) -> i64 {
            2 * k * (k + 1) * (2 * k + 1)
        }
        let (mut l, mut r, mut ans) = (1, 1_000_000, 0);
        while l <= r {
            let m = l + (r - l) / 2;
            if apples(m) >= needed_apples {
                ans = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        8 * ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    minimumPerimeter(neededApples: number): number {
        function apples(k: number): number {
            return 2 * k * (k + 1) * (2 * k + 1);
        }
        let l = 1, r = 1e6, ans = 0;
        while (l <= r) {
            let m = Math.floor(l + (r - l) / 2);
            if (apples(m) >= neededApples) {
                ans = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return 8 * ans;
    }
}

Complexity

  • ⏰ Time complexity: O(log n), where n is the answer for k. Binary search is used to find the minimum k.
  • 🧺 Space complexity: O(1), only a few variables are used for tracking the answer.