Interview Questions

  • View all tutorials
  • blank
  • Implement pow(a,b) without multiplication or division
    This is one type of very common interview question that is usually asked, where your goal is to implement some built-in language function, such as exponentiation, division, hash tables, etc. In this challenge we need to implement exponentiation, or raising a to some power of b which is usually written pow(a, b). In this variation of the challenge, we also need to implement a solution without using the multiplication or division operations, only addition and subtraction are allowed.

    Example of how pow(a, b) works

    Algorithm

    (1) Create a variable named answer (2) Loop from 1 to n (3) Each time through the loop we add a + a + ... (we add a to itself a times) and store result in answer (4) Then each time through the loop we perform step 3 replacing a with answer.

    Code

    // our modified pow function that raises a to the power of b
    // without using multiplication or division
    function modPow(a, n) {
      
      // convert a to positive number
      var answer = Math.abs(a);
      
      // store exponent for later use
      var exp = n;
      
      // loop n times
      while (n > 1) {
        
        // add the previous added number n times
        // e.g. 4^3 = 4 * 4 * 4
        //      4*4 = 4 + 4 + 4 + 4 = 16
        //     16*4 = 16 + 16 + 16 + 16 = 64
        var added = 0;
        for (var i = 0; i < Math.abs(a); i++) { added += answer; }
        answer = added;
        n--;
        
      }
      
      // if a was negative determine if the answer will be
      // positive or negative based on the original exponent
      // e.g. pow(-4, 3) = (-4)^3 = -64
      return (a < 0 && exp % 2 === 1) ? -answer : answer;
      
    }
    
    modPow(2, 10); 
    //modPow(5, 4); 
    //modPow(-4, 7); 
    
    # our modified pow function that raises a to the power of b
    # without using multiplication or division
    def modPow(a, n):
      
      # convert a to positive number
      answer = abs(a)
      
      # store exponent for later use
      exp = n
      
      # loop n times
      while n > 1:
        
        # add the previous added number n times
        # e.g. 4^3 = 4 * 4 * 4
        #      4*4 = 4 + 4 + 4 + 4 = 16
        #     16*4 = 16 + 16 + 16 + 16 = 64
        added = 0
        for i in range(0, abs(a)):
          added += answer
        answer = added
        n -= 1
        
      # if a was negative determine if the answer will be
      # positive or negative based on the original exponent
      # e.g. pow(-4, 3) = (-4)^3 = -64
      if a < 0 and exp % 2 == 1:
        return -answer
      else:
        return answer
    
    print modPow(2, 10)
    #print modPow(5, 4); 
    #print modPow(-4, 7); 
    
    Run Code
    Run Code

    Running time

    The running time for this modified pow function is O(n) where n determines how many times the program will loop calculating a + a + ...

    Sources

    http://www.careercup.com/question?id=2284663
    mrdaniel published this on 11/25/15 | math, Microsoft
    Comments
  • +
  • 1
  • -
  • Using recursion and closure
    function pow(num, e) {
      let exponent;
      let value = num;
    	addup();	
      function addup(outernum = num, iterate = 1) {
        if (iterate == e) {
          return;
        }
        for (let counter = 1; counter < num; counter++) {
          value += outernum;
        }
        exponent = value;
        return addup(value, iterate + 1);
      }
    	return exponent;
    }
    
    Log in to submit a comment.