Write a program to calculate pow(x,n):-

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.

Input : x = 2, n = 3
Output : 8

Input : x = 7, n = 2
Output : 49

Below solution divides the problem into subproblems of size y/2 and call the subproblems recursively.

1. #include<stdio.h>
2.  
3. /* Function to calculate x raised to the power y */
4. int power(int x, unsigned int y)
5. {
6. if (y == 0)
7. return 1;
8. else if (y%2 == 0)
9. return power(x, y/2)*power(x, y/2);
10. else
11. return x*power(x, y/2)*power(x, y/2);
12. }

Time Complexity: O(n)
Space Complexity: O(1)
Algorithmic Paradigm: Divide and conquer.


Above function can be optimized to O(logn) by calculating power(x, y/2) only once and storing it.

1. int power(int x, unsigned int y)
2. {
3. int temp;
4. if( y == 0)
5. return 1;
6. temp = power(x, y/2);
7. if (y%2 == 0)
8. return temp*temp;
9. else
10. return x*temp*temp;
11. }

Time Complexity of optimized solution: O(logn)

Let us extend the pow function to work for negative y and float x.

1. /* Extended version of power function that can work
2. for float x and negative y*/
3. #include<stdio.h>
4.  
5. float power(float x, int y)
6. {
7. float temp;
8. if( y == 0)
9. return 1;
10. temp = power(x, y/2);
11. if (y%2 == 0)
12. return temp*temp;
13. else
14. {
15. if(y > 0)
16. return x*temp*temp;
17. else
18. return (temp*temp)/x;
19. }
20. }
21.  
22. /* Program to test function power */
23. int main()
24. {
25. float x = 2;
26. int y = -3;
27. printf("%f", power(x, y));
28. return 0;
29. }