-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathaToThePowerOfb.java
More file actions
60 lines (54 loc) · 1.16 KB
/
aToThePowerOfb.java
File metadata and controls
60 lines (54 loc) · 1.16 KB
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
package Class02_Recursion;
/*
* Evaluate a to the power of b, assuming both a and
* b are integers and b is non-negative.
*
* Examples
* power(2, 0) = 1
* power(2, 3) = 8
* power(0, 10) = 0
* power(-2, 5) = -32
* power(0,0) = 0
*
* Corner Cases
* What if the result is overflowed?
* We can assume the result will not be overflowed when
* we solve this problem on this online judge.
* */
public class aToThePowerOfb {
public static int power1(int a, int b) {
// base case:
if (a == 0) {
return 0;
}
if (b / 2 == 0) {
return b == 1 ? a : 1;
}
// recursion rule: a^b --> a^(tempB) * a^(b-tempB)
int tempB = b / 2;
int leftRsl = power1(a, tempB);
int rightRsl = power1(a, b - tempB);
return leftRsl * rightRsl;
}
public static long power2(long a, long b) {
// base case:
if (a == 0) {
return 0;
}
if (b / 2 == 0) {
return b == 1 ? a : 1;
}
// recursion rule:
long temp = power2(a, b / 2);
if (b % 2 == 0) {
return temp * temp;
} else {
return a * temp * temp;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
long rsl = power2(11, 0);
System.out.println(rsl);
}
}