Quick Exponentiation
So the problem comes from Daily Coding Problem:
So the secret here is to decompose the exponent (say 10) in its power of 2. So 10 = 8 + 2. Each of these parts can be computed in Log(N) time, which makes the overall execution time for exponentiation some constant * Log(y). Faster than the repeated multiplication. Code is down below, or on GitHub: https://github.com/marcelodebarros/dailycodingproblem/blob/master/DailyCodingProblem11142018.cs
Thanks, Marcelo
This problem was asked by Google.
Implement integer exponentiation. That is, implement the
pow(x, y) function, where x and y are integers and returns x^y.
Do this faster than the naive method of repeated multiplication.
For example,
pow(2, 10) should return 1024.Thanks, Marcelo
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace DailyCodingProblem
{
class DailyCodingProblem11142018
{
public long Exponentiation(long x, long y)
{
long result = 1;
while (y > 0)
{
long exp = x;
long count = 1;
while (count * 2 <= y)
{
exp *= exp;
count *= 2;
}
y -= count;
result *= exp;
}
return result;
}
}
}
This looks like a special case of https://leetcode.com/problems/powx-n My solution is slightly more efficient as it uses fewer variables and as such involves fewer memory copies, but the idea is similar:
ReplyDeleteclass Solution {
public:
double myPow(double x, long n) {
if (n < 0) return 1 / myPow(x, -n);
double result = 1;
for (; n > 0; n /= 2) {
if (n % 2 == 1) result *= x;
x *= x;
}
return result;
}
};
which can be simplified in for the provided problem statement to:
class Solution {
public:
long myPow(long x, long n) {
long result = 1;
for (; n > 0; n /= 2, x *= x) {
if (n % 2 == 1) result *= x;
}
return result;
}
};
which interestingly looks like a valid C# :)
Love the dual-purpose for-loop: control (n) and production (x). Clever!
ReplyDeleteit does not always help, but since I often use guard conditions to avoid deep nesting (interestingly I didn't use it in this case) and using for-loop is a great way to make sure that all post-iteration changes do actually happen. In other words I do this because I'm a very sloppy and it's one of the ways to avoid some common pitfalls :)
Delete