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

Problem

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

Sample Input

x = 2
y = 4

Sample Output

16

Explanation

24 = 16

Approach

We will use a nested loop to solve this problem. This method is very simple and obvious if you know the concept of exponentiation, as shown below. To calculate 24, use the below steps:

1) 2 times add 2, we get 4. (2^2)

2) 2 times add 4, we get 8. (2^3)

3) 2 times add 8, we get 16 (2^4), which is our answer.

Complexity Analysis

The time complexity is O( x ^y ), and the space complexity is O(1)

C++ Programming

#include <bits/stdc++.h>
using namespace std;

// find exponent
int solve(int x, int y)
{
    if (y == 0)
        return 1;

    int ans = x;
    int temp = x;
    int i, j;

    for(i = 1; i < y; i++)
    {
        for(j = 1; j < x; j++)
        {
            ans += temp;
        }
        temp = ans;
    }
    return ans;
}

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

Output

16

Java Programming

import java.io.*;
// implement power function

class Main {
    static int solve(int x, int y)
    {
        if (y == 0)
            return 1;
           
        int ans = x;
        int temp = x;
        int i, j;
        
        for (i = 1; i < y; i++) {
            for (j = 1; j < x; j++) {
                ans += temp;
            }
            temp = ans;
        }

        return ans;
    }

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

Output

16

Python Programming

# implement power function
def solve(x,y):
    if(y==0):
        return 1
        
    ans=x
    temp=x
    
    for i in range(1,y):
        for j in range (1,x):
            ans+=temp
        temp=ans
    return ans

print(solve(2,4))

Output

16

People are also reading:

• Find and remove loops in a Linked List?
• Find minimum jumps required to reach the destination
• Fibonacci Series
• Circular Doubly Linked List
• Breadth First Search- Graph: DSA
• Depth First Search(DFS)- DSA
• Bottom View of a Binary Tree
• Maximum size square sub-matrices with all 1’s
• Modular Exponentiation in Logarithmic Time
• Nth root of M