In this Java post, we will be discussing how to find power of a given number. This approach will be more efficient. In this approach will be using a O(log(n)) time complexity algorithm.
Power of a number AB is the product of A, B times i.e..
AB = A*A*A*A*......(B times).
In this post we will be discussing two methods to find power of given number.
Approach 1:
1. Take the input values of A and B.
2. To retain the values of A and B let us store them in another variables named X and n. And take a variable result which is initialized to 1.
3. Now, iterate a loop till n value reaches to 0(zero).
4. For each iteration in n multiply result with X and reduce the value of n by 1.
5. Finally if n value reaches to zero then we stop this process and then return the result.
int n=B;
int X=A;
int result=1;
while(n>0){
result*=X;
n=n-1;
}
Complexity Analysis:
Time Complexity: O(n). As, we are just iterating the loop just n(=B) times.
Space Complexity: O(1).
Approach 2: In this approach we just use a simple Math logic.
If n value is Even then we multiply the value of X with itself and reduce the value of n to its half here.
Example: AB = A2(B/2) = (A * A)B/2 (when B value is Even).
When B value is 1 (Odd) then we multiply the result with the value of X.
1. Take the input values of A and B.
2. To retain the values of A and B let us store them in another variables named X and n. And take a variable result which is initialized to 1.
3. Now, iterate a loop till n value reaches to 0(zero).
4. For each iteration if n value is Even then we multiply X with itself then we reduce the value of n to its half.
5. And if when n value is odd then we multiply result with X value and then we reduce the value of n by 1.
6. Finally if n value reaches to zero then we return the result.
Complexity Analysis:
Time Complexity: O(log(n)) . Here, we are reducing the value of n to its half. So, we are just iterating the loop by n value. So, time Complexity is reduced to O(log(n)) from O(n).
Space Complexity: O(1)
As we are not using any extra space.
Submitted by Lokeswara Reddy Ajjuguttu (LokeswaraAjjuguttu)
Download packets of source code on Coders Packet
Comments