Volume of pile of cubes

I'm trying a challenge. The idea is the following:

"Your task is to construct a building which will be a pile of n cubes.
The cube at the bottom will have a volume of n^3, the cube above will
have volume of (n-1)^3 and so on until the top which will have a
volume of 1^3.

You are given the total volume m of the building. Being given m can
you find the number n of cubes you will have to build? If no such n
exists return -1"

I saw that apparently:

2³ + 1 = 9 = 3² and 3 - 1 = 2

3³ + 2³ + 1 = 36 = 6² and 6 - 3 = 3

4³ + 3³ + 2³ + 1 = 100 = 10² and 10 - 6 = 4

5³ + 4³ + 3³ + 2³ + 1 = 225 = 15² and 15 - 10 = 5

6³ + 5³ + 4³ + 3³ + 2³ + 1 = 441 = 21² and 21 - 15 = 6

So if I thought, if I check that a certain number is a square root I can already exclude a few. Then I can start a variable at 1 at take that value (incrementing it) from the square root. The values will eventually match or the former square root will become negative.

So I wrote this code:

def find_nb(m):
x = m**0.5
if (x%1==0):
c = 1
while (x != c and x > 0):
x = x - c
c = c + 1

if (x == c):
return c
else:
return -1
return -1


Shouldn't this work? What am I missing?
I fail a third of the sample set, per example: 10170290665425347857 should be -1 and in my program it gives 79863.

Am I missing something obvious?

3 Answers
3

You're running up against a floating point precision problem. Namely, we have

In [101]: (10170290665425347857)**0.5
Out[101]: 3189089316.0

In [102]: ((10170290665425347857)**0.5) % 1
Out[102]: 0.0


and so the inner branch is taken, even though it's not actually a square:

In [103]: int((10170290665425347857)**0.5)**2
Out[103]: 10170290665425347856


If you borrow one of the many integer square root options from this question and verify that the sqrt squared gives the original number, you should be okay with your algorithm, at least if I haven't overlooked some corner case.

(Aside: you've already noticed the critical pattern. The numbers 1, 3, 6, 10, 15.. are quite famous and have a formula of their own, which you could use to solve for whether there is such a number that works directly.)

DSM's answer is the one, but to add my two cents to improve the solution...

This expression from Brilliant.org is for summing cube numbers:

sum of k**3 from k=1 to n:
n**2 * (n+1)**2 / 4


This can of course be solved for the total volume in question. This here is one of the four solutions (requiring both n and v to be positive):

from math import sqrt

def n(v):
return 1/2*(sqrt(8*sqrt(v) + 1) - 1)


But this function also returns 79863.0. Now, if we sum all the cube numbers from 1 to n, we get a slightly different result due to the precision error:

79863.0

v = 10170290665425347857
cubes = n(v) # 79863
x = sum([i**3 for i in range(cubes+1)])

# x = 10170290665425347857, original
x -> 10170290665425347856


I don't know if your answer is correct, but I have another solution to this problem which is waaaay easier

def max_level(remain_volume, currLevel):
if remain_volume < currLevel ** 3:
return -1
if remain_volume == currLevel ** 3:
return currLevel
return max_level(remain_volume - currLevel**3, currLevel + 1)


And you find out the answer with max_level(m, 0). It takes O(n) time and O(1) memory.

max_level(m, 0)

10170290665425347857

Thanks for contributing an answer to Stack Overflow!

But avoid …

To learn more, see our tips on writing great answers.

Required, but never shown

Required, but never shown

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.