Last active
August 10, 2016 14:20
-
-
Save tymofij/9035744 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
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
hi. where can I find the math reasons for that?