# Calculate this multiplication in less than O(n) complexity.

90 views

here is the sample code of problem :
a=100000000,b=200000;
multiplication=1;
while(a--){
multiplication=multiplication*b;
}
printf "multiplication= result"
reduce the time complexity by giving a suitable example which must have less complexity than this for large numbers.

posted Apr 4, 2016

Try to solve it as b^a
actually I need to perform %1000000007 after each step so need any iterative method. In pow() function I used as pow(n%modValue,pow) but it didn't work becuz it is exceeding limit.
Try to use the following formula and D&C with recursion should be O(log n) complexity.

(b^a) mod n = [{b^(a/2) mod n} * {b^(a/2) mod n}] mod n

Let me know if this works for you, if it works I will share the code.
tried recursion method and D&C with  O(log n) . thanks
Do I need to share the code, or you like to share it for the benefit of bigger mass.
okay Sir,I got the  solution and sharing code in answer section

I was facing the same issue and I used this method for multiplication which reduces complexity to O(log n)

`````` int  calculatePower(int n,int p)
{
int h;
if(p==0)
{
return 1;
}
else{
h=calculatePower(n,p/2);
if(p%2==0)
{
return h*h;
}
else{
return n*h*h;
}
}

}
``````