View Discussion
Improve Article
Save Article
View Discussion
Improve Article
Save Article
Method 1 [Using Nested Loops]: We can calculate power by using repeated addition. For example to calculate 5^6.
1]
First 5 times add 5, we get 25. [5^2]
2] Then 5 times add 25, we get 125. [5^3]
3] Then 5 times add 125, we get 625 [5^4]
4] Then 5 times add 625, we get 3125 [5^5]
5] Then 5 times add 3125, we get 15625 [5^6]
C++
#include
using namespace std;
int pow[int a, int b]
{
if [b == 0]
return 1;
int
answer = a;
int increment = a;
int i, j;
for[i = 1; i < b; i++]
{
for[j = 1; j < a; j++]
{
answer += increment;
}
increment = answer;
}
return answer;
}
int main[]
{
cout
Javascript
function pow[a , b]
{
if [b == 0]
return 1;
var answer = a;
var increment = a;
var i, j;
for [i = 1; i < b; i++]
{
for [j = 1; j < a; j++]
{
answer += increment;
}
increment = answer;
}
return answer;
}
document.write[pow[5, 3]];
Output :
125
Time Complexity: O[a * b]
Auxiliary Space:O[1]
Method 2 [Using Recursion]: Recursively add a to get the multiplication of two numbers. And recursively multiply to get a raise to the power b.
C++
#include
using namespace std;
int multiply[int x, int y]
{
if[y]
return [x + multiply[x, y - 1]];
else
return 0;
}
int pow[int a, int b]
{
if[b]
return multiply[a, pow[a, b - 1]];
else
return 1;
}
int main[]
{
cout 0]
return multiply[a, pow[a, b - 1]];
else
return 1;
}
static int multiply[int x, int y]
{
if [y > 0]
return [x + multiply[x, y - 1]];
else
return
0;
}
public static void main[String[] args]
{
System.out.println[pow[5, 3]];
}
}
Python3
def pow[a,b]:
if[b]:
return multiply[a, pow[a, b-1]];
else:
return 1;
def multiply[x, y]:
if [y]:
return [x + multiply[x, y-1]];
else:
return 0;
print[pow[5, 3]];
C#
using System;
class GFG
{
static int pow[int a, int b]
{
if [b > 0]
return
multiply[a, pow[a, b - 1]];
else
return 1;
}
static int multiply[int x, int y]
{
if [y > 0]
return [x + multiply[x, y - 1]];
else
return 0;
}
public static void Main[]
{
Console.Write[pow[5, 3]];
}
}
PHP
Javascript
function pow[a, b]
{
if [b > 0]
return multiply[a, pow[a, b - 1]];
else
return 1;
}
function multiply[x, y]
{
if [y > 0]
return
[x + multiply[x, y - 1]];
else
return 0;
}
document.write[pow[5, 3]];
Output :
125
Time Complexity: O[b]
Auxiliary Space: O[b]
Method 3 [Using bit masking]
Approach: We can a^n [let’s say 3^5] as 3^4 * 3^0 * 3^1 = 3^5, so we can represent 5 as its binary i.e. 101
C++
#include
using namespace std;
long long pow[int a, int n]{
int ans=1;
while[n>0]{
int last_bit = n&1;
if[last_bit]{
ans = ans*a;
}
a = a*a;
n = n >> 1;
}
return ans;
}
int main[] {
cout> 1;
}
return ans;
}
int
main[]
{
printf["%lld",pow_[3,5]];
return 0;
}
Java
import java.io.*;
import java.util.*;
class GFG
{
static int pow[int a, int n]{
int ans = 1;
while[n > 0]
{
int last_bit = n&1;
if[last_bit != 0]{
ans = ans*a;
}
a = a*a;
n = n >> 1;
}
return ans;
}
public static void main[String[] args]
{
System.out.print[pow[3,5]];
}
}
Python3
def pow[a, n]:
ans = 1
while[n > 0]:
last_bit =
n&1
if[last_bit]:
ans = ans*a
a = a*a
n = n >> 1
return ans
print[pow[3, 5]]
C#
using System;
using System.Numerics;
using System.Collections.Generic;
public class GFG {
static int
pow[int a, int n]{
int ans = 1;
while[n > 0]
{
int last_bit = n&1;
if[last_bit != 0]{
ans = ans*a;
}
a = a*a;
n = n >> 1;
}
return ans;
}
public static void Main[string[] args]
{
Console.Write[pow[3,5]];
}
}
Javascript
function pow[a, n]{
let ans = 1;
while[n > 0]
{
let last_bit = n&1;
if[last_bit]
{
ans = ans*a;
}
a = a*a;
n = n >> 1;
}
return ans;
}
document.write[pow[3,5],""];
PHP
Time Complexity: O[log n]
Auxiliary Space: O[1]
Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.