Tags: %TAGME{ tpaction="" web="Main" tag="" }% view all tags

# Leetcode 5 solutions

The C++ pow() function in math.c works on doubles, which you should not use. However, the following integer intPow() function can be used instead:

```int intPow(int base, int exp)
{
int result = 1;
while (exp)
{
if (exp & 1)
result *= base;
exp /= 2;
base *= base;
}
return result;
}```

Solution code:

```#include <iostream>

using namespace std;

long intPow(long base, long exp)
{
int result = 1;
while (exp)
{
if (exp & 1)
result *= base;
exp /= 2;
base *= base;
}
return result;
}

long modExp(long  b, long e, long m) {
if (e==1) {
int r = intPow(b,e) % m;

if (r < 0) cout << "Overflow!!" << endl;
return (r);
}

long e1 = e/2;
long e2 = e - e1;
long r = (modExp(b, e1, m) * modExp(b, e2, m)) % m;

if (r < 0) cout << "Overflow!!" << endl;
return r;

}

int main() {
long b, e, m;
cout << "Modular exponentiation - computes b^e (mod m) " << endl;
cout << "Base (<=10^5): ";
cin >> b;
cout << "Exponent (<=10^5): ";
cin >> e;
cout << "Modulus (<=10^5): ";
cin >> m;

cout << "answer: " << modExp(b, e, m) << endl;

return 0;
}```

### Some test cases

 base exponent modulus b^e % m 34523 23 713 391 43565 335 271 114 43311 3661 51 48 544654 325 5511 1639 12343 32123 211 83 4354 211 23 20 24411 331 533 426 43554 511 411 378 54324 35542 255 21 34563 543255 5331 5304

### Turn in:

1. Complete working program code
2. Runs for all cases above
3. A tight runtime analysis
Topic revision: r1 - 2016-11-14 - JimSkon

 Home Main Web P P View Edit Account
Copyright © 2008-2020 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback