Binary Exponentiation

Write a program to implement Binary Exponentiation.

Example

Input: a = 3,b = 4
Output: 3 ^ 4 is 81

Approach

Java

public class BinaryExponentiation {
    public static void main(String[] args) {
        int a = 3, b = 4;
        int aPowerb = binaryExponentiation(a, b);
        System.out.println(a + " ^ " + b + " is " + aPowerb);
    }

    // Function to find the a^b
    static int binaryExponentiation(int a, int n) {
        // Base Case
        if (n == 0)
            return 1;
        int res = binaryExponentiation(a, n / 2);
        if (n % 2 == 1)
            return res * res * a;
        else
            return res * res;

    }
}

C++

#include <bits/stdc++.h>
using namespace std;
//Function to find the a^b 
int binaryExponentiation(int a,int n)
{
    //Base Case
    if(n==0)
       return 1;
    int res=binaryExponentiation(a,n/2);
    if(n&1)
       return res*res*a;
    else
      return res*res;
    
}
int main()
{
    int a=3,b=4;
    int aPowerb=binaryExponentiation(a,b);
    cout<<a<<" ^ "<<b<<" is "<<aPowerb<<"\n";
    return 0;
}
//Time Complexity: O(log(n))
//Space Complexity :O(1)