Teaching Kids Programming – Find Cubic Root of an Integer (Brute Force, Binary Search Algorithm) – a^3=54872

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:

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:

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:

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.

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:

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