Given two integers n
and x
, your task is to compute nx
— that is, raise n
to the power of x
.
You should implement an efficient solution, preferably using the Binary Exponentiation method.
Assume x
is a non-negative integer.
#include <stdio.h>
long long power(long long n, unsigned int x) {
long long result = 1;
while (x > 0) {
if (x & 1) {
result *= n;
}
n *= n;
x >>= 1;
}
return result;
}
int main() {
long long n = 2;
unsigned int x = 10;
printf("%lld\n", power(n, x)); // Output: 1024
return 0;
}
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(log x) | Binary exponentiation reduces the power x by half in each step, leading to logarithmic time complexity. Even if x is 0, the algorithm performs a constant number of operations. |
Average Case | O(log x) | In the average case, the number of iterations depends on the number of bits in x. For each bit, we either multiply the result or square the base, which is logarithmic in terms of x. |
Worst Case | O(log x) | In the worst case, where x has the maximum number of bits set (e.g., x = 2^k - 1), we still only perform O(log x) multiplications and squarings, maintaining logarithmic time complexity. |
Comments
Loading comments...