Check that smaller cubes fill bigger cube

Check that smaller cubes fill bigger cube

Given one large cube (axis aligned and on integer coordinates), and many
smaller cubes (also axis aligned and on integer coordinates). How can we
check that the large cube is perfectly filled by the smaller cubes.
Currently we check that: 1) For each small cube it is fully contained by
the large cube. 2) That it doesn't intersect any other small cube. 3) The
sum of the volumes of the small cubes equals the volume of the large cube.
This is ok for small numbers of cubes but we need to support this test of
cubes with dimensions greater than 2^32. Even at 2^16 the number of small
cubes required to fill the large cube is large enough that step 2 takes a
while (O(n^2) checking each cube intersects no other).
Is there a better algorithm?