# Implement Power Function InterviewBit Solution

**Problem: **__Implement Power Function__

**Problem Description:**

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.

**For Example**

```
Input : x = 2, n = 3, d = 3
Output : 2
2^3 % 3 = 8 % 3 = 2.
```

## Approach

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)`

**Solution:**

Code in C++