C++ 4ms straightforward iterative O(lg n) solution with explanation


  • 0
    W
    double myPow(double x, int n)
    {
    	if (n == 0) return 1;  // special case
    	if (x == 0) return 0;  // special case
    	
    	double multiplier;
    	double remainder = 1;
    	
    	long long ul_n = n;  // gonna use abs() on n. smallest number will overflow when abs is called on it
    	if (ul_n > 0)
    	{
    		multiplier = x;
    	}
    	else
    	{
    		multiplier = 1.0 / x;
    		ul_n = abs(ul_n);
    	}
    	while (ul_n / 2 > 0)
    	{
    		/*
    		 *  For example, pow(3, 7) becomes
    		 *  start:	3 * 3 * 3 * 3 * 3 * 3 * 3 
    		 *  		9 * 9 * 9 * 3	where 3 is the curRemainder as well as remainder
    		 *  result:	81 * 9 * 3		where 9 is the curRemainder and 9 * 3 is the remainder
    		 */
    		double curRemainder = (ul_n % 2) * multiplier;
    		remainder *= (curRemainder != 0 ? curRemainder : 1);
    		ul_n /= 2;
    		multiplier *= multiplier;
    	}
    	return multiplier * (remainder != 0 ? remainder : 1);
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.