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
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback