top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

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

+2 votes
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 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 %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

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 %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.
Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...