   # 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;
}
}

}
`````` answer Apr 6, 2016
I think u missed the mod part :)
for mod part : use %1000000007 in return statement, like
return (h*h)%1000000007;
&
return (n*h*h)%1000000007; and change int to unsigned long int because function required to perform very large multiplication.
Similar Questions