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.

Examples :

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.

C

#include<stdio.h>
 
/* Function to calculate x raised to the power y */
int power(int x, unsigned int y)
{
    if (y == 0)
        return 1;
    else if (y%2 == 0)
        return power(x, y/2)*power(x, y/2);
    else
        return x*power(x, y/2)*power(x, y/2);
}
 
/* Program to test function power */
int main()
{
    int x = 2;
    unsigned int y = 3;
 
    printf("%d", power(x, y));
    return 0;
}

Java

class GFG {
    /* Function to calculate x raised to the power y */
    static int power(int x, int y)
    {
        if (y == 0)
            return 1;
        else if (y % 2 == 0)
            return power(x, y / 2) * power(x, y / 2);
        else
            return x * power(x, y / 2) * power(x, y / 2);
    }
 
    /* Program to test function power */
    public static void main(String[] args)
    {
        int x = 2;
        int y = 3;
 
        System.out.printf("%d", power(x, y));
    }
}
 
// This code is contributed by Smitha Dinesh Semwal

Python3

# Python3 program to calculate pow(x,n)
 
# Function to calculate x
# raised to the power y 
def power(x, y):
 
    if (y == 0): return 1
    elif (int(y % 2) == 0):
        return (power(x, int(y / 2)) *
               power(x, int(y / 2)))
    else:
        return (x * power(x, int(y / 2)) *
                   power(x, int(y / 2)))
 
# Driver Code
x = 2; y = 3
print(power(x, y))
 
# This code is contributed by Smitha Dinesh Semwal.

C#

using System;
 
public class GFG {
     
    // Function to calculate x raised to the power y
    static int power(int x, int y)
    {
        if (y == 0)
            return 1;
        else if (y % 2 == 0)
            return power(x, y / 2) * power(x, y / 2);
        else
            return x * power(x, y / 2) * power(x, y / 2);
    }
 
    // Program to test function power
    public static void Main()
    {
        int x = 2;
        int y = 3;
 
        Console.Write(power(x, y));
    }
}
 
// This code is contributed by shiv_bhakt.

PHP

<?php
// Function to calculate x 
// raised to the power y
function power($x, $y)
{
    if ($y == 0)
        return 1;
    else if ($y % 2 == 0)
        return power($x, (int)$y / 2) * 
               power($x, (int)$y / 2);
    else
        return $x * power($x, (int)$y / 2) * 
                    power($x, (int)$y / 2);
}
 
// Driver Code
$x = 2;
$y = 3;
 
echo power($x, $y);
     
// This code is contributed by ajit
?>

Output :

 

8

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.

/* 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;
}

Time Complexity of optimized solution: O(logn)

 

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

C

/* Extended version of power function that can work
 for float x and negative y*/
#include<stdio.h>
 
float power(float x, int y)
{
    float temp;
    if( y == 0)
       return 1;
    temp = power(x, y/2);       
    if (y%2 == 0)
        return temp*temp;
    else
    {
        if(y > 0)
            return x*temp*temp;
        else
            return (temp*temp)/x;
    }
}  
 
/* Program to test function power */
int main()
{
    float x = 2;
    int y = -3;
    printf("%f", power(x, y));
    return 0;
}

Java

/* Java code for extended version of power function
that can work for float x and negative y */
class GFG {
     
    static float power(float x, int y)
    {
        float temp;
        if( y == 0)
            return 1;
        temp = power(x, y/2); 
         
        if (y%2 == 0)
            return temp*temp;
        else
        {
            if(y > 0)
                return x * temp * temp;
            else
                return (temp * temp) / x;
        }
    } 
     
    /* Program to test function power */
    public static void main(String[] args)
    {
        float x = 2;
        int y = -3;
        System.out.printf("%f", power(x, y));
    }
}
 
// This code is contributed by  Smitha Dinesh Semwal.

Python3

# Python3 code for extended version
# of power function that can work
# for float x and negative y
 
def power(x, y):
 
    if(y == 0): return 1
    temp = power(x, int(y / 2)) 
     
    if (y % 2 == 0):
        return temp * temp
    else:
        if(y > 0): return x * temp * temp
        else: return (temp * temp) / x
     
# Driver Code
x, y = 2, -3
print('%.6f' %(power(x, y)))
 
# This code is contributed by Smitha Dinesh Semwal. 

C#

// C# code for extended version of power function
// that can work for float x and negative y
 
using System;
 
public class GFG{
     
    static float power(float x, int y)
    {
        float temp;
         
        if( y == 0)
            return 1;
        temp = power(x, y/2); 
         
        if (y % 2 == 0)
            return temp * temp;
        else
        {
            if(y > 0)
                return x * temp * temp;
            else
                return (temp * temp) / x;
        }
    } 
     
    // Program to test function power 
    public static void Main()
    {
        float x = 2;
        int y = -3;
         
        Console.Write(power(x, y));
    }
}
 
// This code is contributed by shiv_bhakt.

PHP

<?php
// Extended version of power
// function that can work
// for float x and negative y
 
function power($x, $y)
{
    $temp;
    if( $y == 0)
    return 1;
    $temp = power($x, $y / 2);     
    if ($y % 2 == 0)
        return $temp * $temp;
    else
    {
        if($y > 0)
            return $x * 
                   $temp * $temp;
        else
            return ($temp * 
                    $temp) / $x;
    }
} 
 
// Driver Code
$x = 2;
$y = -3;
echo power($x, $y);
 
// This code is contributed by ajit
?>

Output :

0.125000