Daily Challenge #55 - Building a Pile of Cubes

Challenge
Your challenge is to construct a building which will be made of 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 with 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 f will be an integer m and you have to return the integer n (such as n^3 + (n-1)^3 + ... + 1^3 = m) or 0 if there is no such n.

Examples
f(1071225) --> 45
f(91716553919377) --> 0

Happy Coding!

---

This challenge comes from g964 on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email [e-mail] with your suggestions!

Comments

[Chris Achard]

I made this one harder than it had to be at first :) I was trying to solve the math problem, but when I switched to just using a loop, it went super quick.

Below is what I came up with in JS, and I recorded my process, so you can watch me solve it! youtu.be/NVA_YuRqscE

const cubes = m => {
  let total = 0
  let n = 0

  while(total < m) {
    n += 1
    total += n**3
  }

  return total === m ? n : 0
}

[Alvaro Montoro]

Nice solution, and nice video explaining it. May I ask, how did you record it?

[Chris Achard]

Thanks!

I have a mac and use screenflow for recording: telestream.net/screenflow/overview...

If you use Windows, then camtasia is very similar: techsmith.com/video-editor.html

I believe QuickTime is a free option for screen recording, but then you still need to do editing somehow.

I make a lot of screencasts, so my mic setup is pretty good (read: expensive :) ) - but you don't need a fancy mic to get started! A lot of headphones (like the base Apple headphones) have pretty good mics in them actually, and then, you can use the audio tools in screenflow to clean it up, or use a service like auphonic.com/ to get some really high quality sound.

Hope that helps!

(I should probably write that up into a blog post so I can just point people to it 😀)

[Alvaro Montoro]

Thanks for the answer. I will give screenflow a try, and maybe get a new headset with microphone.

Btw, that's a blog post I would definitely read/watch. Let me know if you end up posting it.

[Chris Achard]

Will do!

[Dominik G]

Ok, now I got a solution thanks to Wolfram Alpha:

const f = m => {
  var n = (Math.sqrt(8 * Math.sqrt(m) + 1) - 1) / 2;
  return n === Math.floor(n) ? n : 0;
};

[Oleksii Filonenko]

I did the naive iterative solution first, and then I saw the formula from Dominik G, and wanted to compare the two solutions.

Here are the two functions in Rust.

Iterative:

pub fn pile_of_cubes_iterative(m: i64) -> i64 {
    let mut total = 0;
    let mut n: i64 = 0;

    while total < m {
        n += 1;
        total += n.pow(3)
    }

    if total == m {
        n
    } else {
        0
    }
}

Formula:

pub fn pile_of_cubes_formula(m: i64) -> i64 {
    let n = ((8.0 * (m as f64).sqrt() + 1.0).sqrt() - 1.0) / 2.0;
    if n == n.floor() {
        n.floor() as i64
    } else {
        0
    }
}

And a little benchmark (with the number 91716553919377 from the examples):

test tests::pile_of_cubes::bench_formula   ... bench:          34 ns/iter (+/- 2)
test tests::pile_of_cubes::bench_iterative ... bench:       9,900 ns/iter (+/- 20)

Formula is ~290 times faster than the iterative method (for me; your numbers may vary!)

---

A bit of related info: I published my solutions to daily challenges (in Rust) on GitHub - currently days 43-55, but I plan to expand on that :)

[Lalit Vatsal]

Recursive, functional approach using lazy streams in Scala:

  import scala.annotation.tailrec

  def calculate(m: Long): Int = {
    val cubes = Stream.from(1).map(_.toLong).map(i => i * i * i)

    def sumOfFirstXCubes(x: Int): Long = cubes.take(x).sum

    @tailrec
    def rec(i: Int, predicate: Long => Boolean): (Int, Long) = {
      val t = sumOfFirstXCubes(i)
      if (predicate(t)) rec(i + 1, predicate) else (i, t)
    }

    rec(1, _ < m) match {
      case (i, x) if x == m => i
      case _ => 0
    }
  }

[Alvaro Montoro]

It feels like there should be some mathematical formula/pattern that would allow to figure things out without having to loop over all the possible results.

[Dominik G]

I just found that 1³ + 2³ +...+ n³ = (1/4)n² * (n+1)²

So you would need to reverse that.

m=((1/4)n*(n+1))²
sqrt(m)=(1/4)n*(n+1) //given positive n and m
4*sqrt(m)=n*(n+1)

That's as far as I get in my head

[Dominik G]

n = 1/2 (sqrt(1 - 8 sqrt(m)) - 1)

Wolfram alpha to the rescue

[Dominik G]

So my solution would be:

const cubes = m => {
  let n = (Math.sqrt(1 - 8 * Math.sqrt(m)) - 1)/2;

  return n === Math.floor(n) ? n : 0;
}

[Alvaro Montoro]

That's amazing

[Dominik G]

But it doesn't work. :( Just tested it after posting.

[Donald Feury]

Here is a loop based solution, I'm sure there is a formula for finding it but I don't have time right now to figure it out or Go find it.

cubes.go

package cube

// Cubes will determine the count of cubes necessary as n to construct a pile of volume m
// If no amount can equal m, 0 is returned
func Cubes(m int) int {
    var n, total int

    for total < m {
        n++
        total += (n * n * n)
    }

    if total == m {
        return n
    }

    return 0
}

cubes_test.go

package cube

import (
    "testing"
)

var testCases = []struct {
    description string
    input       int
    expected    int
}{
    {
        "challenge example 1",
        1071225,
        45,
    },
    {
        "challenge example 2",
        91716553919377,
        0,
    },
}

func TestCubes(t *testing.T) {
    for _, test := range testCases {
        if result := Cubes(test.input); result != test.expected {
            t.Fatalf("FAIL: %s - Cubes(%d): %d, expected %d", test.description, test.input, result, test.expected)
        }
        t.Logf("PASS: %s", test.description)
    }
}

[maxmattone]

Hoy,
With a reccursive aproach using Emacs Lisp

(cl-defun tower(remainingVol &optional (level 1)) 
  (cond ((< remainingVol 0) 0)
    ((= remainingVol 0) (- level 1))
    (t (tower (- remainingVol (expt level 3)) (+ level 1)))
    )
  )
(tower 1071225)

You might have to increase your max-lisp-eval-depth for great values.