Problem

Implement pow(x, n) % d.

In other words, given x, n and d,

1

find (x^n % d)

Note that remainders on division cannot be negative. In other words, make sure the answer you return is non negative.

Examples

Example 1:

1
2
3

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

Constraints

  • -10^9 <= x <= 10^9
  • 0 <= n <= 10^9
  • 1 <= d <= 10^9

Solution

Method 1 - Using Bits and Divide and Conquer

Reduce n by half till it becomes 0, and each time square the x. Whenever y is odd multiply x with the result, otherwise not.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

int Solution::pow(int x, int n, int d) {
    // If a is 0
    if(x==0) return 0;
    
    long res=1;
    while(n>0){
        // If y is odd, multiply x to the result.
        if(n&1) res = (res*x)%d;
        
        n = n>>1;       // reduce y by half
        
        x = (x*x)%d;    // Since we have reduce y by half, 
                        // that's why we have to square x.
    }
    return (d + res)%d;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

public int pow(int x, int n, int d) {
	if (x == 0) {
		return 0;
	}
	long a1 = x % d;
	long p = 1;
	while (n > 0) {
		if ((n & 1) == 1) {
			p = (p * a1) % d;
		}
		n /= 2;
		a1 = (a1 * a1) % d;
	}
	if (p < 0) {
		return (int) ((p + d) % d);
	} else {
		return (int) p;
	}
}

Complexity

  • ⏰ Time complexity: O(log n)
  • 🧺 Space complexity: O(1)