DEV Community

dev.to staff
dev.to staff

Posted on

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 yo+challenge@dev.to with your suggestions!

Top comments (16)

Collapse
 
chrisachard profile image
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
}
Collapse
 
alvaromontoro profile image
Alvaro Montoro

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

Collapse
 
chrisachard profile image
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 😀)

Thread Thread
 
alvaromontoro profile image
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.

Thread Thread
 
chrisachard profile image
Chris Achard

Will do!

Collapse
 
dominikfg profile image
Dominik G • Edited

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;
};
Collapse
 
brightone profile image
Oleksii Filonenko • Edited

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 :)

Collapse
 
lprakashv profile image
Lalit Vatsal • Edited

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
    }
  }
Collapse
 
alvaromontoro profile image
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.

Collapse
 
dominikfg profile image
Dominik G • Edited

I just found that 13 + 23 +...+ n3 = (1/4)n2 * (n+1)2

So you would need to reverse that.

m=((1/4)n*(n+1))2
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

Collapse
 
dominikfg profile image
Dominik G • Edited

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

Wolfram alpha to the rescue

Thread Thread
 
dominikfg profile image
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;
}
Thread Thread
 
alvaromontoro profile image
Alvaro Montoro

That's amazing

Thread Thread
 
dominikfg profile image
Dominik G

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

Collapse
 
dak425 profile image
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)
    }
}

Collapse
 
mattonem profile image
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.