Interview Questions

Quickly calculate the cube root of 6 digit numbers

The is a clever interview question that asks you to calculate the cube root of a number quickly. We can solve this by some mathematical tricks that won't require any calculates to take place, only table lookups. This algorithm will focus on calculating the cube root of 6 digit numbers (or less). For example, if the input is **636056** then your program should output **86**.
## Algorithm

The general algorithm is as follows:
(1) Store the first 10 **cube roots**, their **cubes**, and the **last digit** in the number.
(2) Ignore the last 3 digits of the input number, and for the remaining numbers, find the **cube** in the table that is less than or equal to the remaining number, and take the corresponding **cube root** to be the first number in your answer.
(3) For the last 3 digits that you previously ignored, loop through the table and when you get to the i^{th} index, where i equals the last digit of the remaining 3 numbers, take the corresponding number in the right column as your answer.
(4) These numbers combined are the cube root answer.
## Example 1

If the input is 148877.
(1) A table has been created.
(2) After ignoring the last 3 digits, we are left with 148. The largest cube less than this number is 125, and the corresponding cube root is **5**.
(3) For the last 3 digits, 877, the last number is 7. When we get to the 7^{th} index in the table, we see that the last column number is **3**.
(4) The cube root of 148877 is therefore: **53**.
## Example 2

If the input is 830584.
(1) A table has been created.
(2) After ignoring the last 3 digits, we are left with 830. The largest cube less than this number is 729, and the corresponding cube root is **9**.
(3) For the last 3 digits, 584, the last number is 4. When we get to the 4^{th} index in the table, we see that the last column number is **4**.
(4) The cube root of 830584 is therefore: **94**.
## Code

## Running time

This algorithm runs in O(1) time because the running time does not depend on the size of the number, but on the size of the list of cubes we store, which is a small constant number.
## Sources

http://www.careercup.com/question?id=5709026522300416

function fastCubeRoot(num) { var cubes_10 = { '0': 0, '1': 1, '8': 8, '27': 7, '64': 4, '125': 5, '216': 6, '343': 3, '512': 2, '729': 9 }; // get last 3 numbers and the remaining numbers var arr = num.toString().split(''); var last = arr.slice(-3); var first = parseInt(arr.slice(0, -3).join('')); // answer will be stored here var lastDigit = 0, firstDigit = 0, index = 0; // get last digit of cube root for (var i in cubes_10) { if (index === parseInt(last[last.length-1])) { lastDigit = cubes_10[i]; } index++; } // get first digit of cube root index = 0; for (var i in cubes_10) { if (parseInt(i) <= first) { firstDigit = index; } index++; } // return cube root answer return firstDigit + '' + lastDigit; } fastCubeRoot(830584);

def fastCubeRoot(num): # python dicts are unordered so we store the # elements in dicts within an array cubes_10 = [ {'0': 0}, {'1': 1}, {'8': 8}, {'27': 7}, {'64': 4}, {'125': 5}, {'216': 6}, {'343': 3}, {'512': 2}, {'729': 9} ] # get last 3 numbers and the remaining numbers arr = list(str(num)) last = arr[-3:] first = int(''.join(arr[0:-3])) # answer will be stored here lastDigit = 0 firstDigit = 0 index = 0 # get last digit of cube root for i in range(0, len(cubes_10)): if index == int(last[len(last)-1]): lastDigit = cubes_10[i].get(cubes_10[i].keys()[0]) index += 1 # get first digit of cube root index = 0 for i in range(0, len(cubes_10)): if int(cubes_10[i].keys()[0]) <= first: firstDigit = index; index += 1 # return cube root answer return str(firstDigit) + '' + str(lastDigit) print fastCubeRoot(830584)

mrdaniel
published this on 11/24/15 **|**

1

This is a neat trick, but does it have any practical application? The link, unless I missed something, has examples of much more general answers to the question.
The impractical aspect of the above approach is that it gives arbitrarily wrong answers if the input is not an exact cube. Seems like know that a number is an exact cube is a harder question that getting the cube root once you already know that.
Am I missing something or is this just a fun trick?

numbergames

commented on 09/29/16

0

@numbergames, yes this is more of a clever trick to quickly calculcate the cube root of larger numbers. In reality you would just implement a fast (liner time or sublinear time) algorithm to calculcate any cube root.

mrdaniel

commented on 09/29/16

Login to submit a comment