ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

Implement pow(x, n), which calculates x raised to the power n (x^n) in C++

prodevelopertutorial August 20, 2018
Example 1:
Input: 2.00000, 10
Output: 1024.00000

Achieve it within O(log n)

This problem can be solved in 4 different ways:

  1. Recursive
  2. Iterative
  3. Divide and Conquer
  4. Bit Manipulation

We shall look at the first 3 methods.

So let us understand how pow(x ^ n)  means.

It means, multiplies “x” with “n” “x’s”.

2 ^3 = 2 * 2 * 2 = 8

or multiply (n-1) times.

This can be achieved easily by using for loop.

for ( i = 1; i <= n; i ++)

                  result = result * x;

This solution will give time complexity of O(n).

But according to the question we need to achieve it with O(log n).

1. Using Recursion

So this can be achieved by using the below formula:

For “x^n”

If n is even then calculate (pow (x ^ (n/2)) * pow(x ^(n/2))).

If n is odd then calculate (x * pow(x ^ n/2)). This is because, in the odd case, we return 1. In the below example, in pass 4, I have explained the concept.

Example:

pow (2 ^ 8)

Pass 1:
In Even case x = 2 n = 8 x * x = 4 n/2 = 4
Pass 2:
 In Even case x = 4 n = 4 x * x = 16 n/2 = 2
Pass 3:
In Even case x = 16 n = 2 x * x = 256 n/2 = 1
Pass 4:
In odd case x = 256 n = 1 x * x = 65536 n/2 = 0

As n is 0. The recursion function will return 1. Hence the final result will be 256.

The result is 256

2. Divide and Conquer

In this solution, we follow the same above procedure and we do it iteratively instead of recursively.

Solution in C++

#include<iostream>

using namespace std;


double get_pow_recursive(double x, int n) 
{
	// base case
    if(n == 0)
       	return 1;

    // check if n is negative
    if(n<0)
    {
        n = -n;
       	x = 1/x;
    }

    // check if n is even or odd
    if(n%2 == 0)
    {
    	return get_pow_recursive(x*x, n/2);
    }
    else
    {
    	return  x*get_pow_recursive(x*x, n/2);
    }
}


double get_pow_divide_conquer(double x, int n) 
{
	double result =1;
	while(n != 0)
    {
    	if(n%2 == 0)
        {        
			x = x*x;
			n /= 2;
		}
		else
		{
			if(n>0)
			{
				result *= x;
				n--;
			}
			else
			{
				result/=x;
				n++;
			}
		}
	}
        return result;
}


int main()
{
	int x = 2;
	int n = 8;
	double result = 0;

	//result = get_pow_recursive(x, n);
	result = get_pow_divide_conquer(x, n);

	cout<<"The result is "<<result<<endl;

	return 0;
}

 

Output:

The result is 256

List Of Tutorials available in this website:

C Programming 20+ ChaptersC++ Programming 80+ Chapters
100+ Solved Coding QuestionsData Structures and Algorithms 85+ Chapters
System design 20+ ChaptersShell Scripting 12 Chapters
4g LTE 60+ ChaptersMost Frequently asked Coding questions
5G NR 50+ ChaptersLinux System Programming 20+ chapters
Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2020 ProDeveloperTutorial.com
Get top courses from: Educative.io