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

Posted in

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

Vinay Khatri
Last updated on September 26, 2022

    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 0 = 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:

    Tags:
    operator

    Leave a Comment on this Post

    0 Comments