Friday, 28 August 2015

Compute 'x' raised to power 'n' in O(logN) time using Java

Hello friends,

In  continuation to the recursive algorithms, I am here with you with another problem.

Suppose we have a number 'x' a another positive Integer 'n'. We need to find the value of 'x' raised to power to 'n'.

Friends please find below the code in java for this.

package com.recursion.power;


import java.util.Scanner;

/**
*
* @author krishna.k
*
*         This class computes the value of 'x' raised to power of 'n' in time
*         complexity of O(log n). 'x' is Integer, and n is a positive Integer
*         including 0.
*
*
*
*
*/
public class PowerComputation {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the value of x (base)");
        int x = sc.nextInt();
        System.out.println("Enter a positve integer n (power)");
        int n = sc.nextInt();
        System.out.println("Value of " + x + " raised to power " + n + " is " + computePower(x, n));
    }

    public static int computePower(int x, int n) {
        if (x == 0 || x == 1 || n == 1) {
            return x;
        }
        if (n == 0) {
            return 1;
        }
        int temp = computePower(x, n / 2);
        if (n % 2 == 0) {
            return temp * temp;
        } else {
            return x * temp * temp;
        }
    }
}