Implement power function without using multiplication & division operators (Recursive Approach)

Problem

Given two positive integers x and y, implement x ^y without using multiplication or division operator

Sample Input

x = 2
y = 3

Sample Output

8

Explanation

23 = 8

Approach

We will use the below properties of exponents to solve this problem:

1. x ^y = x * x ^y-1
2. x ⁰ = 1

The above properties resemble recursion as the second property is the base condition and according to the first property we can get x ^y by adding x ^y-1 upto x times.

Complexity Analysis

The time complexity is O(max(x, y)) with space complexity O(y) due to the call stack.

C Programming

#include <stdio.h>
// implement power function
int solve(int x, int y)
{
 // base case
    if (y == 0) {
        return 1;
    }

    int ans = 0;

    //recursive call
    int exp = solve(x, y - 1);

    for (int i = 0; i < x; i++) {
        ans += exp;
    }
    return ans;
}

void main()
{
    printf("%d", solve(2, 3));
}

Output

8

C++ Programming

#include <iostream>
using namespace std;

// implement power function
int solve(int x, int y)
{
 // base case
    if (y == 0) {
        return 1;
    }

    int ans = 0;
    int exp = solve(x, y - 1);   //recursive call

    for (int i = 0; i < x; i++) {
        ans += exp;
    }
    return ans;
}

int main()
{
    cout << solve(2, 3);
    return 0;
}

Output

8

Java Programming

class Main
{
    // implement power function
    public static int solve(int x, int y)
    {
    // base case
        if (y == 0) {
            return 1;
        }

        int ans = 0;
        int exp = solve(x, y - 1);   // recursive call

        for (int i = 0; i < x; i++) {
            ans += exp;
        }

        return ans;
    }

    public static void main(String[] args) {
        System.out.print(solve(2, 3));
    }
}

Output

8

Python Programming

# implement power function
def solve(x, y):
    # base case
    if y == 0:
        return 1

    exp = solve(x, y - 1)  #recursive call

    ans = 0
    for i in range(x):
        ans += exp

    return ans

print(solve(2, 3))

Output

8

People are also reading:

• Rod Cutting Problem
• Longest subarray with sum as K
• Merge Two Sorted Arrays in-place
• Program to Rotate an Array
• Sort binary array in linear time
• Find LCM and HCF of two numbers
• Subarray with Sum k
• Find Maximum Subarray Sum
• Longest? ?Bitonic? ?Subarray? ?Problem?
• Dutch National Flag Problem