Skip to content

1954. Minimum Garden Perimeter to Collect Enough Apples 👍

  • Time: $O(\log 10^5) = O(1)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
 public:
  long long minimumPerimeter(long long neededApples) {
    long long l = 1;
    long long r = 100'000;  // \sqrt [3] {10^{15}}

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

    return l * 8;
  }

 private:
  // Returns the # of apples at k-th level.
  //    k := the level making perimeter = 8k
  // p(k) := # of apples at k-th level on the perimeter
  // n(k) := # of apples at 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 # of apples at k-th level should be
  //   k(k+1)(2k+1)/2 * 4 = 2k(k+1)(2k+1)
  long long numApples(long long k) {
    return 2 * k * (k + 1) * (2 * k + 1);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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 # of apples at k-th level.
  //    k := the level making perimeter = 8k
  // p(k) := # of apples at k-th level on the perimeter
  // n(k) := # of apples at 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 # of apples at 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);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
  def minimumPerimeter(self, neededApples: int) -> int:
    # Returns the # of apples at k-th level.
    #    k := the level making perimeter = 8k
    # p(k) := # of apples at k-th level on the perimeter
    # n(k) := # of apples at 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 # of apples at k-th level should be
    #   k(k+1)(2k+1)//2 * 4 = 2k(k+1)(2k+1)
    def numApples(k: int) -> int:
      return 2 * k * (k + 1) * (2 * k + 1)

    return bisect.bisect_left(range(100_000), neededApples,
                              key=lambda m: numApples(m)) * 8