Building a Pile of Cubes

I was playing with some code challenges and found one called Building a Pile of Cubes. While there is a naïve, linear-time solution, with a little bit of mathematics we can find a far more elegant, constant-time solution to the problem.

The general idea is that we are building a tower made of \(n\) cubes where we are given the total volume of the tower, \(V\). Building from the bottom up, the base block of our tower should have a volume of \(n^3\), the next with a volume of \((n-1)^3\), and so forth, until the top block which should have a volume of \(1^3\). We are tasked with finding \(n\), the number of blocks, if it is possible to match the construction pattern with the total volume, \(V\).

By definition, a cube has equal length, width, and breadth, and we can compute the volume, \(V\), of a cube with side \(\ell\) by multiplying the length, width, and breadth,

There is a naïve coding solution that can be applied by starting with \(n = 1\), iteratively increasing \(n\) by \(1\), and retaining the total sum of each additional volume until the total volume has been reached or exceeded. If the final sum equals the provided volume, then we have found the number of blocks.

As an aside, we should generally avoid single-character variable names in code, but I used s since sum is an existing function in Julia and, for the sake of clarity, I’m using the variables n and V to match the equations I’ve used in this post.

function naive_cubepile(V)
    n = 1
    s = n
    while s < V
        n += 1
        s += n^3
    end
    return s == V ? n : nothing
end

There is a much more efficient way to solve this challenge. Re-stating this mathematically, \(V\) is the total volume of our pile where our solution is \(n\). We use the partial sums formula to write it as,

With some algebra, this can be re-written into its quadratic form,

which we can solve using the quadratic formula. This yields

Since this is quadratic we have two solutions – notice the \(\pm\) above. However, the volume can’t be negative, \(V \geq 0\), which means \(\sqrt{1 + 8\sqrt{V}}\) is always greater than \(-1\). We can ignore the second solution and write our function to use the solution where the second term of the numerator is positive.

function cubepile(V)
    n = (sqrt(1 + 8 * sqrt(V)) - 1) / 2
    n == floor(n) ? Int(n) : nothing
end

It’s not hard to convince ourselves that a simple computation will be much more efficient than a large number of iterations, \(O(1)\) versus \(O(n)\), but we’ll benchmark the example solutions from the challenge to see how much more efficient it actually is.

@time cubepile(1071225)
>  0.000000 seconds
@time cubepile(4183059834009)
>  0.000000 seconds
@time cubepile(135440716410000)
>  0.000000 seconds

@time naive_cubepile(1071225)
>  0.000001 seconds
@time naive_cubepile(4183059834009)
>  0.000001 seconds
@time naive_cubepile(135440716410000)
>  0.000003 seconds

Computers are fast and the Julia language is really fast too, so we don’t even register a reading for any of our computed version runs while the naïve version takes \(1 \times 10^{-6}\) seconds for the first two runs and \(3 \times 10^{-6}\) seconds for the last. This is a great example of where we can use mathematics to create a more scalable solution to the problem, especially if \(n\) is very large.