Interview Questions

  • View all tutorials
  • blank
  • 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 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)   
    
    Run Code
    Run 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
    mrdaniel published this on 11/24/15 | math, Google
    Comments
  • +
  • 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?
  • +
  • 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.
    Login to submit a comment