Power of a Number, Modulo 10⁹ + 7
Solve this ProblemMedium20–25 min
Topics
MathBit ManipulationNumber Theory
Companies
Practice:GFG ↗AmazonMicrosoftGoogleAdobe
Given an integer base
x and a non-negative integer exponent n, compute xn modulo 10⁹ + 7 — the value wraps under a large prime modulus so the true (potentially astronomically large) result always fits in an ordinary integer.
Repeated multiplication works but costs one multiplication per unit of n. Binary exponentiation reduces that to one squaring per bit of n — turning up to a billion multiplications into about thirty — by observing that xn can be built from x1, x2, x4, x8, ..., the doubling powers that correspond to each bit of n's binary representation.
Test Case 1:
Input:x = 2, n = 10
Output:1024
Explanation:2¹⁰ = 1024, well under the modulus — no wraparound needed here.
Test Case 2:
Input:x = 2, n = 32
Output:294967268
Explanation:2³² = 4294967296, which exceeds 10⁹ + 7, so the true value wraps around under the modulus.
Test Case 3:
Input:x = -2, n = 3
Output:999999999
Explanation:(-2)³ = -8. Since the result must be non-negative, -8 is normalized to (10⁹ + 7) - 8.
Constraints
- ◆
-1000 ≤ x ≤ 1000 - ◆
0 ≤ n ≤ 10⁹ - ◆
Return the answer modulo 10⁹ + 7
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Repeated Multiplication
BruteMultiply the base into a running result, one factor at a time, n times — taking the modulus after every multiplication so the running value never grows unbounded. Correct, but for n close to 10⁹ this is up to a billion individual multiplications.
Time
O(n)Space
O(1) extraJava
1class Solution {
2 public int power(int x, int n) {
3 final int MOD = 1000000007;
4 long base = ((long) x % MOD + MOD) % MOD;
5 long result = 1;
6 for (int i = 0; i < n; i++) {
7 result = (result * base) % MOD;
8 }
9 return (int) result;
10 }
11}Optimal — Binary Exponentiation
OptimalWalk through the bits of n from least significant to most. Every round, square the base — after k rounds it holds x raised to 2^k — and whenever the current bit of n is 1, fold that squared value into the result. This visits one round per bit of n instead of one multiplication per unit of n, turning a billion iterations into about thirty.
Time
O(log n)Space
O(1) extraJava
1class Solution {
2 public int power(int x, int n) {
3 final int MOD = 1000000007;
4 long base = ((long) x % MOD + MOD) % MOD;
5 long result = 1;
6 long e = n;
7 while (e > 0) {
8 if ((e & 1) == 1) {
9 result = (result * base) % MOD;
10 }
11 base = (base * base) % MOD;
12 e >>= 1;
13 }
14 return (int) result;
15 }
16}