Calculate a^n (a power of n) in O(logn)

   We can always calculate A^N by multiplying A with A N times.

    ans=1;

    for(i=1;i<=n;i++)

    {

            ans=ans*a;

     }

This will take O(n) time. There is another way of calculating A^N in O(logn) time.

We can translate the code above in a different way.

    ans=1;   

    while(n>0)

    {

         ans=ans*a;

         n=n-1;

     }

The code above "means" subtract 1 from n until it reaches 0 and in the same time multiply the answer with a.

As we know from our math classes A^B*A^B=(A^B)^2= A^(2*B).  Using this we can cut our N into half (if it is an even number) and instead of multiplying our answer with a we will simply multiply our answer by itself. 

   ans=1;   

    while(n>0)

    {

         if(n%2==0)

         {

               ans=ans*ans;

               n=n/2;

         {

         else

         {

               ans=ans*a;

               n=n-1;

          }

     }

The code is generally right , but there is one problem. If n is divisible on 2 from the beginning we will get a wrong answer because of the following.

when ans=1  and n%2==0 ( n is divisible by 2) we will cut n into half but the answer won't change becuase 1*1=1

   So we better  begin with ans=a and n=n-1

    ans=a;

    n=n-1;  

    while(n>0)

    {

         if(n%2==0)

         {

               ans=ans*ans;

               n=n/2;

         {

         else

         {

               ans=ans*a;

               n=n-1;

          }

     } 

IF YOU HAVE ANY QUESTION LEAVE THEM IN COMMENTS. NO QUESTION WILL BE UNANSWERED