Interview Questions

  • View all algorithm 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
  • +
  • 2
  • -
  • 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; }
  • +
  • 1
  • -
  • Can someone explain further why time complexity is O(n) when there's two loops in the solution ?
  • +
  • 0
  • -
  • I think the complexity is quadratic, because a more reasonable definition of the input size would be max(a, n). Without fixing 'a' the running time as a function of 'n' is unbounded, so it doesn't make sense to try and determine O(n).
  • +
  • 0
  • -
  • It's O(n) because it's fixed, it'll always be base * exponent number of iterations. Another way to look at it is even when changing the input the algorithm still scales linearly, which is essentially what O(n) means, ie (0,0) -> (1,0) -> (0,1) ->(1,1)->(1, 2)->..., takes 0, 0, 0, 1, 2, ..., steps.
    Log in to submit a comment.