This is the challenge I participated in more text on the 7th day, event details see: more text challenge

### The integer power of the value (the sword refers to Offer 16)

#### Title description

Realize pow( *x* , *n* ) , that is, calculate the n-th power function of x (ie, xn). Do not use library functions, and do not need to consider the issue of large numbers.

Example 1:

Input: x = 2.00000, n = 10 Output: 1024.00000 Copy code

Example 2:

Input: x = 2.10000, n = 3 Output: 9.26100 Copy code

Example 3:

Input: x = 2.00000, n = -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = 0.25 Copy code

**prompt**

- -100.0 <x <100.0
- -2^31 <= n <= 2^31-1
- -10^4 <= xn <= 10^4

#### Thinking analysis

The problem requires that library functions cannot be used. We can consider using recursion to achieve this problem, because n has both positive and negative numbers. Consider the positive number first, when the positive number is odd,${x^n = x^(n/2) * x^(n/2) * x}$ , when it is an even number${x^n = x^(n/2) * x^(n/2)}$. In this way, we can decompose step by step until n = 0, pow = 1, as the termination condition.

#### Code display

Solution 1: The time complexity is${O(logn)}$ , the space complexity is${O(1)}$ .

```
public double myPow ( double x, int n) {
if (n >= 0 ){
return rPow(x,n);
} else {
return 1/(rPow(x,-(n + 1 )) * x); //The maximum value of an integer and the minimum value of a negative number are not symmetrical -231 <= n <= 231-1
}
}
public double rPow ( double x, int n) {
if (n == 0 ){
return 1 ;
}
double rPow = rPow(x,n/2 );
if (n% 2 == 0 ){
return rPow * rPow;
} else {
return rPow * rPow * x;
}
}
Copy code
```

### Recursive Multiplication (Interview Question 08.05)

#### Title description

Recursive multiplication. Write a recursive function, without using the * operator, to achieve the multiplication of two positive integers. You can use plus, minus, and displacement, but be stingy.

Example 1:

Input: A = 1, B = 10 Output: 10 Copy code

Example 2:

Input: A = 3, B = 4 Output: 12 Copy code

**prompt**

- Ensure that the multiplication range will not overflow

#### Thinking analysis

The title requires that we cannot use multiplication, and try to minimize the use of plus, minus, and displacement. Therefore, we should not write the way of adding a number that is recursively repeated. The local is the same as the integer number of the above. The square problem is very similar, but here is addition. When B is odd,${A * B = A * (B/2) * A * (B/2) * B}$ . When it is an even number,${A * B = A * (B/2) * A * (B/2)}$ . B keeps decreasing until B=1 as the termination condition. At the same time, there is a small optimization. Find the minimum value of A and B, and use the minimum value as the number of additions and the maximum value as the value of each addition, so that the number of additions will be reduced.

#### Code display

Solution 1: The time complexity is${O(logn)}$ , the space complexity is${O(1)}$ .

```
public int multiply ( int A, int B) {
//if (A == 1){
//return B;
//}
//int value = multiply(A/2,B);
//if (A% 2 == 0){
//return value + value ;
//} else {
//return value + value + B;
//}
//optimize
int max = Math.max(A,B);
int min = Math.min(A,B);
if (min == 1 ){
return max;
}
int value = multiply(min/2 ,max);
if (min% 2 == 0 ){
return value + value;
} else {
return value + value + max;
}
}
Copy code
```

### summary

The focus of these two questions is to master how odd and even numbers are decomposed. To master this, it is not difficult to find using recursion.