Math.Pow

MathPow

using System;

// Implement pow(x, n)

namespace Math.Power
{
    public class Program
    {
        public static void Main(string[] args)
        {
            test1(2, 3);
            test1(2, -3);
            test1(2, -4);
            
        	test2(2, 3);
            test2(2, -3);
            test2(2, -4);
        }
        
        static void test1(int x, int n) {
            Console.WriteLine("Pow({0}, {1}): Actual: {2}", x, n, pow1(x, n));
        }
        
    	static void test2(int x, int n) {
            Console.WriteLine("Pow({0}, {1}): Actual: {2}", x, n, pow2(x, n));
        }
        
        // Time: O(n)
        // Space: O(1)
        static double pow1(int x, int n) {
            double result = 1;
            
            double operand = x;
               
            bool isNegative = false;
               
            if (n < 0) {
                operand = (1 / operand);
                n *= -1;
                isNegative = true;
            }
            
            for (int i = 0; i < n; i++) {
                result *= operand;
            }
            
            if (isNegative && (n % 2 != 0)) {
                result *= -1;
            }
            
            return result;
        }
        
        // Time: O(logn)
        // Space: O(n) because of the call stack
        static double pow2(int x, int n) {
            double operand = x;
               
            bool isNegative = false;
               
            if (n < 0) {
                operand = (1 / operand);
                n *= -1;
                isNegative = true;
            }
            
            double result = pow2Helper(operand, n);
            
            if (isNegative && (n % 2 != 0)) {
                result *= -1;
            }
            
            return result;
        }
       
        static double pow2Helper(double x, int n) {
            if (n == 0) {
                return 1;
            }
                       
            double result = pow2Helper(x, n/2);
            
            if (n % 2 == 0) {
                result *= result;
            } else {
                result = result * result * x;
            }
            
            return result;
        }
    }
}