Skip to content

Instantly share code, notes, and snippets.

@tymofij
Last active August 10, 2016 14:20
Show Gist options
  • Save tymofij/9035744 to your computer and use it in GitHub Desktop.
Save tymofij/9035744 to your computer and use it in GitHub Desktop.
import math
def cube_root(x):
# negative number cannot be raised to a fractional power
res = math.copysign(abs(x) ** (1.0/3), x)
# 64 ** (1/3.0) gives us 3.9999999999999996
# and it breaks things up pretty bad. let's try finding int one
rounded_res = int(round(res))
if rounded_res ** 3 == x:
res = rounded_res
return res
def n_cubes(a, b):
""" count number of cubes in the range of A, B. borders included
"""
cube_equal_or_greater_than_a = int(math.ceil(cube_root(a)))
cube_equal_or_smaller_than_b = int(math.floor(cube_root(b)))
if cube_equal_or_smaller_than_b >= cube_equal_or_greater_than_a:
return cube_equal_or_smaller_than_b - cube_equal_or_greater_than_a + 1
return 0
assert n_cubes(8, 65) == 3
assert n_cubes(8, 64) == 3
assert n_cubes(9, 12) == 0
assert n_cubes(8, 12) == 1
assert n_cubes(8, 8) == 1
assert n_cubes(0, 1) == 2
assert n_cubes(0, 0) == 1
assert n_cubes(-1, 0) == 2
assert n_cubes(-1, 1) == 3
assert n_cubes(-8, -2) == 1
assert n_cubes(-65, -8) == 3
assert n_cubes(-64, -8) == 3
@draconar
Copy link

hi. where can I find the math reasons for that?

@tymofij
Copy link
Author

tymofij commented Jul 1, 2015

one can notice that x³ > y³ for any x > y. (that is called monotonic function)
therefore for any x that lies in ∛A ≤ x ≤ ∛B, cube would fit: A ≤ x³ ≤ B

So to get number of cubes which lie within A..B, you can simply count number of integers between ∛A and ∛B. And number of integers between two numbers is their difference.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment