top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

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

+2 votes
622 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 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button
Try to solve it as b^a
actually I need to perform %********** 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

1 Answer

0 votes

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 by Shivam Kumar Pandey
I think u missed the mod part :)
for mod part : use %********** in return statement, like
return (h*h)%**********;
&
return (n*h*h)%**********; and change int to unsigned long int because function required to perform very large multiplication.
...