Teaching Kids Programming: Videos on Data Structures and Algorithms
Example: Find the integer cubic root of a^3=54872
First of all, we need to find out how many digits of a, which is easy to find out. “a” is a 2-digit number since 54872 is between 10^3 and 100^3.
Also, the digit at One is 8, because 8^3 ends 2 and all other digits to the power of 3 don’t end at 2.
So we can bruteforce the digit at ten, which only gives 9 choices:
1 2 3 4 5 6 7 8 9 | ans = -1 for i in range(1, 10): num = (i * 10 + 8)**3 if num == 54872: print(f"{i * 10 + 8}^3={(i * 10 + 8)**3}") ans = num break if ans == -1: print("Can't find the integer for a**3=54872") |
ans = -1 for i in range(1, 10): num = (i * 10 + 8)**3 if num == 54872: print(f"{i * 10 + 8}^3={(i * 10 + 8)**3}") ans = num break if ans == -1: print("Can't find the integer for a**3=54872")
We can check the first few values:
10^3=1000
20^3=8000
30^3=27000
40^3=64000
Therefore, 54872 is between 30^3 and 40^3 thus, the answer is 38.
Bruteforce Algorithm to Find the Integer Cubic Root
Obviously, we can bruteforce to find the integer cubic root. We can try the integers up to a if we want to find the answer to a^3=x where x is known and a is integer. Here we go:
1 2 3 4 5 | def integer_root(x): for i in range(x + 1): if i ** 3 == x: return i return -1 ## not found |
def integer_root(x): for i in range(x + 1): if i ** 3 == x: return i return -1 ## not found
Note, we can use the next function (syntax sugar) to make the implementation concise:
1 2 | def integer_root(N): return next((i for i in range(N + 1) if i ** 3 == N), -1) |
def integer_root(N): return next((i for i in range(N + 1) if i ** 3 == N), -1)
The time complexity is O(N)
Actually, we don’t need to try all integers up to x. We can optimize the range by trying up to the cube root of x instead of x itself. Testing integers larger than the cube root of x would be unnecessary since their cubes would exceed x.
1 2 3 | import math def integer_root(N): return next((i for i in range(int(math.isqrt(N)) + 1) if i ** 3 == N), -1) |
import math def integer_root(N): return next((i for i in range(int(math.isqrt(N)) + 1) if i ** 3 == N), -1)
The time complexity is O(Sqrt(N)).
Binary Search Algorithm to Find the Integer Cubic Root
We can use binary search algorithm to find the cube root of an integer x more efficiently. Here’s how we can do it:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | def integer_root(N): if x < 0: return -1 # Handle negative numbers if needed low, high = 0, N while low <= high: mid = (low + high) // 2 mid_cubed = mid ** 3 if mid_cubed == N: return mid elif mid_cubed < N: low = mid + 1 else: high = mid - 1 return -1 # No integer cube root found |
def integer_root(N): if x < 0: return -1 # Handle negative numbers if needed low, high = 0, N while low <= high: mid = (low + high) // 2 mid_cubed = mid ** 3 if mid_cubed == N: return mid elif mid_cubed < N: low = mid + 1 else: high = mid - 1 return -1 # No integer cube root found
low starts at 0 and high starts at N (or some other reasonable maximum). In each iteration of the binary search, we calculate the middle value mid and compare mid**3 to N. The search space is halved in each step, making it more efficient than a linear search. Time Complexity: Binary search runs in O(log N), which is much faster than the O(∛N) complexity of a linear search up to the cube root of N.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Modern C++ Language Features