-
Notifications
You must be signed in to change notification settings - Fork 85
/
061.py
32 lines (21 loc) · 609 Bytes
/
061.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
"""
Problem:
Implement integer exponentiation. That is, implement the pow(x, y) function, where x
and y are integers and returns x^y.
Do this faster than the naive method of repeated multiplication.
For example, pow(2, 10) should return 1024.
"""
def pow(base: int, power: int) -> int:
if power == 0:
return 1
if power % 2 != 0:
return pow((base * base), power // 2) * base
return pow((base * base), power // 2)
if __name__ == "__main__":
print(pow(2, 10))
print(pow(3, 4))
"""
SPECS:
TIME COMPLEXITY: O(log(n))
SPACE COMPLEXITY: O(log(n)) [recursion depth]
"""