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

By | November 28, 2021

Problem

Given two positive integers x and y, implement xy 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. xy = x * xy-1
  2. x0 = 1

The above properties resemble recursion as the second property is the base condition and according to the first property we can get xy by adding xy-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:

Vamware
Author: Vinay

I am a Full Stack Developer with a Bachelor's Degree in Computer Science, who also loves to write technical articles that can help fellow developers.

Leave a Reply

Your email address will not be published. Required fields are marked *