Problem statement

https://leetcode.com/problems/building-boxes/

Solution

The idea is that we need to build our boxes in tethahedral numbers. That is first we create pyramid of size 1 with 1 box, then size 2 with 4 boxes, size 3 with 10 boxes, size 4 with 20 boxes and so on. When we do not have boxes for full layer, we need to start to work with triangle numbers: 1, 3, 6, 10, ... . So we have two steps:

  1. Find maximum layer of pyramid: biggest k, such that k*(k+1)*(k+2)//6 <= n.
  2. On the next step we find maximum triangle number l, such that l*(l+1)//2 <= new n

Complexity

It is O(n^(1/3)) for time and O(1) for space. If we have used binary search it whould have been O(log n).

Code

class Solution:
    def minimumBoxes(self, n):
        for k in range(n+1):
            if k*(k+1)*(k+2) > 6*n: break
                
        n -= (k-1)*k*(k+1)//6
        for l in range(n+1):
            if l*(l+1) >= 2*n: break
                
        return k*(k-1)//2 + l