How to get the correct output in Modulo (10^9 + 7) format?

Question

I am working on this code challenge:

Problem Description

Given 2 integers x and n, you have to calculate x to the power of n, modulo 10^9+7 i.e. calculate (x^n) % (10^9+7).

In other words, you have to find the value when x is raised to the power of n, and then modulo is taken with 10^9+7.

a%b means the remainder when a divides b. For instance, 5%3 = 2, as when we divide 5 by 3, 2 is the remainder.

Note that 10^9 is also represented as 1e9.

Input format One line of input containing two space separated integers, x and n.

Output format Print the required answer.

Sample Input 1 100000000 2

Sample Output 1 930000007

Explanation 1 (10^8)^2 = 10^16

10^16 % (10^9+7) = 930000007

Constraints 0 <= x < 10^9

0 <= n < 10^5

Code

The following is my code:

import java.util.*;

class ModularExponentiation {
    // NOTE: Please do not modify this function
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int n = sc.nextInt();

        int ans = modularExponentiation(x, n);
        System.out.println(ans);
    }

    // TODO: Implement this method
    static int modularExponentiation(int x, int n) {
        int M = 1000000007;
        long a = (long) Math.pow(x, n);

        long b = a%M;

        return (int)b;
    }
}

When I run my code, it succeeds for the sample test case and an edge case, but fails for 3 base cases. How do I make my code succeed all test cases?

Answer 1

I am trying to make it bit more simple:

 /**
 * Intuition:
 * 1. 2^8 = 2^4 * 2^4, where n = 8 (an even number) => p * p, where p is the power value.
 * 2. 2^9 = 2^4 * 2 * 2^4, where n = 9 (an odd number) => p * x * p
 * 3. as Andrey B. Panfilov already mentioned in the previous post, (x * x) % mod = ((x % mod) * (x % mod)) % mod
 */

int mod = 1000000007;
long result = 0;

public int pow(int x, int n) {
    if(n == 0)
        return 1; // x^0 = 1
    else if(n == 1)
        return x; // x^1 = x
    else {
        int p = pow(x, n >> 1); // n >> 1 = n/2
        if((n & 1) == 0)
            return ((p % mod) * (p % mod)) % mod;
        else
            return ((p % mod) * x * (p % mod)) % mod;
    }
}

As every time we are dividing the n by 2, the time complexity will be O(log n), similar as Binary Search.

Answer 2

If you have problem in C++ then , you can use

const unsigned int Mod=1e9+7;

Answer 3

Does this work?

    public static int modularExponentiation(int x, int n) {
        int modulo = 1000000007;
        if (n == 0) {
            return 1;
        } else if (n == 1) {
            return x % modulo;
        } else if (n == -1) {
            return 1 / x;
        }
        int p = modularExponentiation(x, n >> 1);
        long product = ((long) p * p) % modulo;
        return (int) (product * modularExponentiation(x, n & 1) % modulo);
    }

---

Key points:

1. Math.pow(x,n) suffers from overflow and we can't compensate that overflow relying on result only, that is why initial idea of Math.pow(x,n) % modulo produces wrong results
2. We may notice that (x * x) % modulo == (x % modulo) * (x % modulo) % modulo, and it is safe to use long here as intermediate result because x % modulo < modulo and modulo * modulo < 2^63 - 1
3. We need to reconstruct the process, but naive approach that x^n is a product of n x's is too slow - it has O(N) time complexity, however we may notice that x^2k == (x^k)^2 and x^(2k+1) == x * (x^k)^2 - so we may use either recursion here or loop to achieve O(LogN) time complexity

alternative loop solution:

    public static int modularExponentiation(int x, int n) {
        int modulo = 1000000007;
        long product = 1;
        long p = x;
        while (n != 0) {
            if ((n & 1) == 1) {
                product = product * p % modulo;
            }
            p = (p * p % modulo);
            n >>= 1;
        }
        return (int) product;
    }