# Compute the value of A raise to the power B using Fast Exponentiation

Here, we are going to **compute the value of A raise to the power B using Fast Exponentiation**.

Submitted by Ankit Sood, on December 05, 2018

Now here we are going to learn that **how to compute the value of a^b i.e. "A" raise to the power "B" using an optimized algorithm called as "fast-exponentiation"**?

we could have used a brute force approach to do the required task but then it would have taken **O(b)** i.e a brute force approach can solve the required task in linear time whereas the same task could be done in **O(log b)** using **FAST–EXPONENTIATION**.

**Fast exponentiation** uses a simple recursive approach whose recurrence relation can be written as :

**F(a,b) = F(a,b/2)*F(a,b/2)**

From the above recurrence relation, it can be easily seen that the time complexity would be **O(log b)**.

## C++ program to find the value of A^B using fast exponentiation

#include <iostream> using namespace std; //function to find a^b int fcheck(int a,int b){ if(b == 0) return 1; if(b == 1) return a; return fcheck(a,b/2)*fcheck(a,b/2); } //main code int main(){ int a,b; cout<<"Enter the first number (value of a): "; cin>>a; cout<<"Enter the second number (Value of b): "; cin>>b; int x=fcheck(a,b); if(b%2==0 || b==1) cout<<a<<" raise to the power "<<b<<" is = " <<x<<endl; else cout<<a<<" raise to the power "<<b<<" is = " <<a*x<<endl; return 0; }

**Output**

First run: Enter the first number (value of a): 5 Enter the second number (Value of b): 3 5 raise to the power 3 is = 125 Second run: Enter the first number (value of a): 5 Enter the second number (Value of b): 0 5 raise to the power 0 is = 1 Third run: Enter the first number (value of a): 5 Enter the second number (Value of b): 1 5 raise to the power 1 is = 5

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions