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.