CODEWITHSUNDEEP
javaalgorithmmath
Nitin Singhal
Nitin Singhal

Reputation: 55

calculate kth power of 2

I was solving a problem and the basic idea to calculate the power of 2 for some k. And then multiply it with 10. Result should be calculated value mod 10^9+7.

Given Constraints 1≤K≤10^9

I am using java language for this. I used 'Math.pow' function but 2^10000000 exceeds its range and I don't want to use 'BigInteger' here. Any other way to calculate such large values.

The actual problem is:

For each valid i, the sign with number i had the integer i written on one side and 10K−i−1 written on the other side.

Now, Marichka is wondering — how many road signs have exactly two distinct decimal digits written on them (on both sides in total)? Since this number may be large, compute it modulo 10^9+7.

I'm using this pow approach, but this is not an efficient way. Any suggestion to solve this problem.

My original Solution: 

/* package codechef; // don't place package name! */

import java.util.*;
class Codechef
{
 public static void main (String[] args) throws java.lang.Exception
{
    Scanner scan = new Scanner(System.in);
    int t = scan.nextInt();
    while(t-->0){
        long k = scan.nextInt();
        long mul=10*(long)Math.pow(2, k-1);
        long ans = mul%1000000007;

        System.out.println(ans);
    }
  }
}

After taking some example, I reached that this pow solution works fine for small constraints but not for large. 

while(t-->0){
        long k = scan.nextInt();
        long mul=10*(long)Math.pow(2, k);
        long ans = mul%1000000007;

        System.out.println(ans);
    }

This pow function is exceeding its range. Any good solution to this.

Upvotes: 0

Views: 1846

Answers (3)

Faruk Hossain
Faruk Hossain

Reputation: 1203

You need to use the idea of dividing the power by 2.

long bigmod(long p,long e,long M) {
    if(e==0)
        return 1;
    if(e%2==0) {
        long t=bigmod(p,e/2,M);
        return (t*t)%M;
    }
    return (bigmod(p,e-1,M)*p)%M;
}

while(t-->0){
        long k = scan.nextInt();
        long ans = bigmod(2, k, 1000000007);
        System.out.println(ans);
    }

You can get details about the idea from here: https://www.geeksforgeeks.org/how-to-avoid-overflow-in-modular-multiplication/

Upvotes: 2

het jagani
het jagani

Reputation: 47

As the size of long is 8 bytes and it is signed datatype so the range of long datatype is -(2^63) to (2^63 - 1). Hence to store 2^100 you have to use another datatype.

Upvotes: -1

Amadan
Amadan

Reputation: 198294

Basically, f(g(x)) mod M is the same as f(g(x) mod M) mod M. As exponentiation is just a lot of multiplication, you can just decompose your single exponentiation into many multiplications, and apply modulo at every step. i.e.

10 * 2^5 mod 13

is the same as

10
* 2 mod 13
* 2 mod 13
* 2 mod 13
* 2 mod 13
* 2 mod 13

You can compact the loop by not breaking up the exponentiation so far; i.e. this would give the same answer, again:

10
* 4 mod 13
* 4 mod 13
* 2 mod 13

Faruk's recursive solution shows an elegant way to do this.

Upvotes: 5

Related Questions