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:
1^3 + 2^3 + ... + n^3is 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 because
nwill always be positive. So
n(n+1)/2 = sqrt(m).
n(n+1) = 2*sqrt(m). This problem is essentially asking us to find two consecutive numbers,
n+1, such that their product is equal to
target = 2*math.sqrt(m)
for n in range(1, int(math.sqrt(target))+1):
if n*(n+1) == target:
Here, I've defined
target to be
2*sqrt(m). I'm looping from
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+1, whose product equals the target.
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.
In yet another attempt, I tried doing the most straightforward solution possible: looping from
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
So I tried looping from
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.
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?