Hackerrank Nov Challenge – Power of Large Numbers

PROBLEM STATEMENT

In a nutshell, we have a^b mod 10^9 + 7 ( ^ denotes power )

Range of a & b: 1 <= a,b <= 10^100000

PRE – REQUISITES

FERMAT’S THEOREM:

The theorem stats that, if is a prime number, then for any arbitrary integer 

a^p \equiv a \pmod p.

MODULAR EXPONENTIATION:

Consider example of finding 5^13. 13 in binary format is 1101.

5^13 can split-ted into 5^8  *  5^*5^1

Pseudo code:

int findPower(base,power)

{

if( power % 2 == 1 )

res = res * base

power = power / 2

base = base * base

}

MODULAR ARITHMETIC

We need to aware of basic arithmetic properties like (a*b) mod m = ( (a mod m) * ( b mod m ) ) mod m

SOLUTION:

First step is we need to reduce both base and power so that they fit in the 32 – integer range.

Base value greater than 1o^9 + 7 can reduced by taking Modulo 1o^9 + 7. Based on Fermat’s theorem, Power value can be reduced by taking Modulo 10^9+6.

After reducing them to integers, find base^power using Modular Exponentation

CODE:

#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

#define MOD (1000000007)

int findPow(int base,int power)
{
    int ans = 1,basePower = base;

    while( power > 0)
    {
        if( (power&1) == 1 )
            ans = ( (long long int)ans * (long long int)basePower ) % (MOD);

        basePower = ((long long int)basePower * (long long int)basePower) % (MOD);
        power = power>>1;
    }

    return ans;
}

int findRem(string a,int num)
{
    int sz = a.size(),i=0,rem=0,temp=0;
    while( i < sz )
    {
        rem = ( ( (long long int)rem * 10LL ) % (num) + (a[i]-'0') ) % (num);
        i++;
    }
    return rem;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    int t;
    cin>>t;
    string a,b;
    while(t--)
    {
        cin>>a>>b;

        int x = findRem(a,(MOD));
        int y = findRem(b,(MOD-1));
        cout<<findPow(x,y)<<endl;
    }
    return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s