Program to calculate pow(x, n) using Divide and Conqueror approach
To solve the problem follow the below idea:
There is a problem with the above solution, the same subproblem is computed twice for each recursive call. We can optimize the above function by computing the solution of the subproblem once only.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Function to calculate x raised to the power y in O(logn)int power(int x, unsigned int y){ int temp; if (y == 0) return 1; temp = power(x, y / 2); if (y % 2 == 0) return temp * temp; else return x * temp * temp;}/*Driver code */int main(){ int x = 2; // Base unsigned int y = 3; // Exponent int result = power(x, y); std::cout << result << std::endl; return 0;} |
Output
8
Time Complexity: O(log n)
Auxiliary Space: O(log n), for recursive call stack
C++ Program To Calculate the Power of a Number
Write a C++ program for a given two integers x and n, write a function to compute xn. We may assume that x and n are small and overflow doesn’t happen.
Examples :
Input : x = 2, n = 3
Output : 8Input : x = 7, n = 2
Output : 49
Contact Us