InterviewBit-Solutions/Programming/BinarySearch/PowerFunction.java at master · garv-cmd/InterviewBit-Solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
package BinarySearch;

/**
 * Author - archit.s
 * Date - 03/10/18
 * Time - 11:48 AM
 */
public class PowerFunction {

    public int pow(int x, int n, int d) {

        long res = 1;

        if(x == 0){
            return 0;
        }

        if(n == 0){
            return 1;
        }

        boolean flag = false;
        if(x < 0){
            x = Math.abs(x);
            if(n%2 == 1){
                flag = true;
            }
        }

        long temp = x%d;

        while(n > 0){
            if((n&1) == 1){
                res = (res*temp)%d;
            }

            temp = (temp*temp)%d;

            n = n>>1;
            if(res > d){
                res = res%d;
            }
        }

        if(flag){
            return d - (int)res;
        }

        return (int)res;
    }

}