3
$\begingroup$

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. The summation 1^3 + 2^3 + ... + n^3 is equal to [n(n+1)/2]^2 = m.

  2. Taking the square root of both sides yields |n(n+1)/2| = sqrt(m). We can disregard the absolute value sign because n will always be positive. So n(n+1)/2 = sqrt(m).

  3. Therefore, n(n+1) = 2*sqrt(m). This problem is essentially asking us to find two consecutive numbers, n and n+1, such that their product is equal to 2*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:

enter image description here

enter image description here

enter image description here

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?

$\endgroup$
7
  • $\begingroup$ @kelalaka Sorry? Not sure what you mean. Could you clarify? $\endgroup$ Dec 4, 2018 at 11:30
  • 2
    $\begingroup$ If $n^2+n=2\sqrt{m}$, $n^2+n-2\sqrt{m}=0$, $n=\frac{-1±\sqrt{1+8\sqrt{m}}}{2}$ $\endgroup$ Dec 4, 2018 at 11:34
  • $\begingroup$ @DanielCastle Right, but how does that address the issue of floating-point imprecision? I'll run into the same problem if I take that approach. $\endgroup$ Dec 4, 2018 at 11:37
  • $\begingroup$ if $(n^2+n)^2 = 4 m$ to avoid the floating point issue. $\endgroup$
    – kelalaka
    Dec 4, 2018 at 11:37
  • 1
    $\begingroup$ Also in your screenshots 2*sqrt(m) = m for some reason? $\endgroup$ Dec 4, 2018 at 13:16

2 Answers 2

3
$\begingroup$

Here is a Python function that is about as simple as possible and as fast as possible, assuming the input is valid.

def find_nb(m):
    return int(math.sqrt(2 * (math.sqrt(1.0 * m))))

If the input can be invalid, such as 10252519345963644753026 in the question, and the function should return None accordingly, the Python program can be the following.

def find_nb(m):
    # Use float since math.sqrt is wrong for big integers.
    target = int(math.sqrt(2 * (math.sqrt( 1.0 * m))))
    # or target = int(1.4142135623730951 * m ** 0.25)

    if (target * (target + 1) // 2) * (target * (target + 1) // 2) == m:
        return target
    else:
        return None

What is happening? According to Daniel Castle's comment, for $m\ge1$,

$$ n=\frac{-1+\sqrt{1+8\sqrt{m}}}{2}=\frac{-1}2+\sqrt{\frac14+2\sqrt{m}} $$ It can be checked easily that $$ n + 0.4 < \sqrt{2\sqrt m} < n + 0.5$$

That means, $n = \lfloor \sqrt{2\sqrt m} \rfloor$ with plenty of room to prevent an error.

$\endgroup$
2
  • $\begingroup$ Passes all test cases. $\endgroup$ Dec 6, 2018 at 19:52
  • $\begingroup$ As expected. :) $\endgroup$
    – John L.
    Dec 6, 2018 at 20:09
-1
$\begingroup$

Use the ideas of your first approach, but complete them with binary search in order to avoid floating point computations. Start with a large enough interval such as $[a,b] = [0, \lceil m^{1/3} \rceil]$ in which you search for the correct value of $n$ (if it exists). Test $n = \lfloor (a+b)/2 \rfloor$:

  • If $n^2 (n+1)^2 > 4m$ then you need to look in $[a,n-1]$; update $b$.

  • If $n^2 (n+1)^2 < 4m$ then you need to look in $[n+1,b]$; update $a$.

  • If $n^2(n+1)^2=4m$ you are done.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.