Interview Questions

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

## 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

(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.

// 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);

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

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;
}
```

jaitthomas

commented on 02/21/17

1

Can someone explain further why time complexity is O(n) when there's two loops in the solution ?

heron182

commented on 12/24/18

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).

tobwin

commented on 07/05/19

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.

akoaysigod

commented on 12/31/18

Log in to submit a comment.