Problem: Implement Power Function
Implement pow(x, n) % d.
Note that remainders on division cannot be negative. In other words, make sure the answer you return is non-negative.
Input : x = 2, n = 3, d = 3 Output : 2 2^3 % 3 = 8 % 3 = 2.
The approach is pretty simple and straight forward.
Reduce y by half till it becomes 0, and each time square the x.
Whenever y is odd multiply x with the result, otherwise not.
Time & Space Complexity
Time complexity: O(logN), here N is y
Space complexity: O(1)
Code in C++