Sunday 26 June 2016

Calculate the power in log(n) complexity in Java

Using divide and conquer:


public class PowerUsingDnC {
     public static void main(String[] args) {
           int x = 5;
           int n = 7;

           /** To calculate the power of x^n. */
           int result = power(x,n);
          
           System.out.println(result);
     }

     private static int power(int x, int n) {
           int temp = 1;

           if(n==0) {
                return 1;
           }

           int result = 1;

           /** divide using original power function. */
           temp = power(x, n/2);

           /** conquer using temp value. */
           if(n%2==0) {
                result = temp*temp;
           } else {
                result = temp*temp*x;
           }
           return result;
     }
}

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...