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 ith 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 7th 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 4th index in the table, we see that the last column number is 4. (4) The cube root of 830584 is therefore: 94.

## Code

```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 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 str(firstDigit) + '' + str(lastDigit)

print fastCubeRoot(830584)
```

## 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
mrdaniel published this on 11/24/15 |
• +
• 2
• -
• 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?
• +
• 1
• -
• or simply by using an array: ```def fastCubeRoot(num): cubes_10 = [0,1,8,27,64,125,216,343,512,729] fd=0 ld=0 frst=int(str(num)[:3]) last=int(str(num)[3:]) for k in cubes_10: if k <= frst: fd=cubes_10.index(k) if cubes_10.index(k) == last%10: ld=k%10 return (fd*10)+ld print(fastCubeRoot(830584))```
• +
• 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.
• +
• 0
• -
• Java
```import java.util.*;

public class Main {
public static ArrayList<Integer> cubes_10 = new ArrayList<Integer>();
public static void main(String[] args) throws Exception {
// create the look up table
int val;
for (int i = 0; i <= 9; i++) {
val = (int)Math.pow(i, 3);
System.out.printf("%d = %dn", val, (val % 10));
}

fastCubeRoot(148877);
fastCubeRoot(830584);
}

public static int fastCubeRoot(int num) {

int first = num / (int)Math.pow(10, 3);
int firstDigit = 0, lastDigit = 0;

// get the last digit of cube root
lastDigit = cubes_10.get(num % 10) % 10;

// get the fist digit of cube root
int index = 0;
for (Integer preCalc : cubes_10) {
if (preCalc <= first) {
firstDigit = index;
}
index++;
}

int answer = firstDigit * 10 + lastDigit;
System.out.printf("cube root (%d) = %dn", num, answer);
• For Python 3: ```def fastCubeRoot(num): cubes_10 = [ {0: 0}, {1: 1}, {8: 8}, {27: 7}, {64: 4}, {125: 5}, {216: 6}, {343: 3}, {512: 2}, {729: 9} ] fd=0 ld=0 frst=int(str(num)[:3]) last=int(str(num)[3:]) for k in cubes_10: if list(k)[0] <= frst: fd=cubes_10.index(k) if cubes_10.index(k) == last%10: ld=list(k)[0]%10 return (fd*10)+ld print(fastCubeRoot(830584))```