After reading this article , You can go and get the following questions :
-----------
Today, let's talk about a topic related to mathematical operations ,LeetCode 372 topic Super Pow, Let you do a huge power operation , Then find the remainder .
int superPow(int a, vector<int>& b);
Ask your algorithm to return power operations a^b
The calculation results of 1337 modulus (mod, That's the remainder ) After the results of the . You have to calculate the power first a^b
, But this b
It will be very big. , therefore b
In the form of an array .
This algorithm is actually a modular power algorithm widely used in discrete mathematics , As for why we should be right 1337 We don't care , There are three difficulties in this problem alone :
One is how to deal with indexes represented by arrays , Now? b
Is an array , in other words b
It can be very large , There's no way to go straight to integer , Otherwise, it may overflow . How do you use this array as an index , Do the calculation ?
The second is how to get the result after module ? According to the truth , At least we should calculate the result of power operation first , Then I do % 1337
This operation . But the problem is , Exponentiation you know , The real results are bound to be terrifying , in other words , There is no way to show the true result , It's a long time ago .
Third, how to perform power operation efficiently , There are also algorithmic skills in power operation , If you don't understand the algorithm , I'll explain later .
So for these questions , Let's think separately , Break one by one .
PS: I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating . Recommended collection , Write the title in the order of my article , Master all kinds of algorithm set, then put into the sea of questions, like fish .
How to deal with array index
First of all, clarify the problem : Now? b
Is an array , It can't be expressed as an integer , And the characteristic of array is random access , Deleting the last element is more efficient .
Don't consider the requirement of module , With b = [1,5,6,4]
For example , The law of exponentiation , We can find such a law :
See this , Our old readers must have been acutely aware of , This is the sign of recursion ! Because the scale of the problem has shrunk :
superPow(a, [1,5,6,4])
=> superPow(a, [1,5,6])
that , Found this Law , We can simply translate the code framework first :
// Calculation a Of k Result of the power
// We will implement it manually later
int mypow(int a, int k);
int superPow(int a, vector<int>& b) {
// Recursive base case
if (b.empty()) return 1;
// Take out the last number
int last = b.back();
b.pop_back();
// Simplify the original problem , Reduce the scale recursively solve
int part1 = mypow(a, last);
int part2 = mypow(superPow(a, b), 10);
// Merge the results
return part1 * part2;
}
Come here , It's not hard to understand ! We have solved b
It's an array problem , Now let's see how to deal with mod, Avoid integer overflow caused by too large result .
How to deal with it mod operation
First of all, clarify the problem : Because of the way computers code , Form like (a * b) % base
Operations like this , The result of multiplication can lead to overflow , We hope to find a skill , Can simplify this expression , Avoid spillovers and get results .
For example, in binary search , Let's use (l+r)/2
Turn it into l+(r-l)/2
, Avoid spillovers and get the right results .
that , Let's talk about the technique of modular operation , After all, modular operations are more common in algorithms :
(a * b) % k = (a % k)(b % k) % k
The proof is simple , hypothesis :
a = Ak +B;b = Ck + D
among A,B,C,D
It's an arbitrary constant , that :
ab = ACk^2 + ADk + BCk +BD
ab % k = BD % k
Again because :
a % k = B;b % k = D
therefore :
(a % k)(b % k) % k = BD % k
Sum up , Then we can get the equation that we simplify the module .
let me put it another way , Module the result of multiplication , It's equivalent to first modulus every factor , And then we can get the modulus of the result of factor multiplication .
So extend to this question , To find the power of a number is not to multiply the number ? So just expand the ideas just now , You can modulo a power operation :
int base = 1337;
// Calculation a Of k Then the power and base The result of module
int mypow(int a, int k) {
// To model a factor
a %= base;
int res = 1;
for (int _ = 0; _ < k; _++) {
// There's multiplication , It's a potential spillover point
res *= a;
// Module the result of multiplication
res %= base;
}
return res;
}
int superPow(int a, vector<int>& b) {
if (b.empty()) return 1;
int last = b.back();
b.pop_back();
int part1 = mypow(a, last);
int part2 = mypow(superPow(a, b), 10);
// Modules are required for every multiplication
return (part1 * part2) % base;
}
You see , First pair factor a
modulus , And then every time I do the multiplication res
modulus , This ensures res *= a
When the code is executed, both factors are less than base
Of , It will not cause overflow , At the same time, the result is correct .
thus , This problem has been completely solved , You can pass LeetCode The question system of .
But some readers may ask , Is this algorithm for power so simple , Direct one for Cycle and multiply ? Will it be more complicated , Is there a more efficient algorithm ?
There are more efficient algorithms , But in this case alone , That's enough .
Because you think about , call mypow
Function passed in k
How big... At most ?k
But is b
A number in an array , That is to say 0 To 9 Between , So it can be said that every call here mypow
The complexity of time is O(1). The time complexity of the whole algorithm is O(N),N by b
The length of .
But when it comes to power operations , Let's say by the way how to calculate power operation efficiently .
PS: I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating . Recommended collection , Write the title in the order of my article , Master all kinds of algorithm set, then put into the sea of questions, like fish .
How to find power efficiently
There is more than one algorithm for fast exponentiation , Let's talk about a basic idea we should master . Using the properties of power operation , We can write such a recursion :
This idea is definitely better than using it directly for It's efficient to find the power of a cycle , Because there is an opportunity to directly scale the problem (b
Size ) Cut it in half , The complexity of the algorithm must be log The magnitude of .
Then you can modify the previous mypow
function , Translate this recursive formula , Plus the modular operation :
int base = 1337;
int mypow(int a, int k) {
if (k == 0) return 1;
a %= base;
if (k % 2 == 1) {
// k Is odd
return (a * mypow(a, k - 1)) % base;
} else {
// k It's even
int sub = mypow(a, k / 2);
return (sub * sub) % base;
}
}
Although for the subject , There is no obvious efficiency improvement in this optimization , But the power algorithm has been upgraded , In the future, if someone asks you to write a power algorithm , At least write the algorithm .
thus ,Super Pow Even if it's completely solved , Including the idea of recursion and the processing of modular operations 、 The skill of power operation , It can be said that this topic is quite interesting , What interesting topic do you have , May as well leave a message to share .
_____________
my Online e-books Yes 100 Original articles , Hands with brushes 200 Daoli is the subject , Recommended collection ! Corresponding GitHub Algorithm Repository We've got it 70k star, Welcome to mark star !