I'm working on solving an algorithm problem defined as follows (important parts in bold):
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?
The parameter of the function findNb will be an integer m and you have to return the integer n such as n^3 + (n-1)^3 + ... + 1^3 = m if such a n exists or -1 if there is no such n.
Okay, so here's how I've been approaching the problem from a theoretical standpoint:
The summation
1^3 + 2^3 + ... + n^3
is equal to[n(n+1)/2]^2 = m
.Taking the square root of both sides yields
|n(n+1)/2| = sqrt(m)
. We can disregard the absolute value sign becausen
will always be positive. Son(n+1)/2 = sqrt(m)
.Therefore,
n(n+1) = 2*sqrt(m)
. This problem is essentially asking us to find two consecutive numbers,n
andn+1
, such that their product is equal to2*sqrt(m)
.
My code
def find_nb(m):
target = 2*math.sqrt(m)
for n in range(1, int(math.sqrt(target))+1):
if n*(n+1) == target:
return n
return -1
Here, I've defined target
to be 2*sqrt(m)
. I'm looping from n=1
to n=sqrt(target)
(inclusive) because there is no point in going beyond the square root of the target when trying to find two numbers, n
and n+1
, whose product equals the target.
The issue...
This code runs into floating-point precision issues that are fairly consistent across all tests that failed. Here are some screenshots of tests that failed:
Notice that in all of these cases, the value I end up returning is 1 less than the value I stopped looping at. This is quite odd, and I'm not sure what could be causing this behavior.
If you compute the values using a good calculator, you'll find that it is indeed an issue of floating-point imprecision. I'm not sure how to deal with that. My code fails for 33/69 test cases.
Alternative approach
In yet another attempt, I tried doing the most straightforward solution possible: looping from n=1
to n=m
and calculating [n(n+1)/2]^2
for each iteration, then comparing this to m
. And, unsurprisingly, that solution is not accepted because it takes too long to execute for very large values of m
!
So I tried looping from n=1
to n=sqrt(m)
to at least simplify the range of values I'm working with. But clearly, the exponentiation, division, and multiplication add up in terms of complexity, and thus this revised approach also results in an execution timeout.
Question
How am I supposed to solve this problem? Is it possible to solve this problem without introducing floating-point errors and without the algorithm taking an unreasonable amount of time for large input values?