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.

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

// store exponent for later use
var exp = n;

// loop n times
while (n > 1) {

// e.g. 4^3 = 4 * 4 * 4
//      4*4 = 4 + 4 + 4 + 4 = 16
//     16*4 = 16 + 16 + 16 + 16 = 64
for (var i = 0; i < Math.abs(a); i++) { added += answer; }
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

# store exponent for later use
exp = n

# loop n times
while n > 1:

# e.g. 4^3 = 4 * 4 * 4
#      4*4 = 4 + 4 + 4 + 4 = 16
#     16*4 = 16 + 16 + 16 + 16 = 64
for i in range(0, abs(a)):
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:
else:

print modPow(2, 10)
#print modPow(5, 4);
#print modPow(-4, 7);
```

## 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 |
• +
• 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.