CareerCup

#include "ConditionalCompilationMacro.h"
#include <stdio.h>

static int count = 0;

unsigned int APowerN(unsigned int A, unsigned int N)
{
int tempA = 0;

if(N > 1)
{
tempA = A;
A = A*A;
A = APowerN(A, N/2);
//A *= APowerN(tempA, N%2);
if(1 == (N%2))
{
A *= tempA;
count++;
}
count++;
}
else
{
if(0 == N)
{
count++;
return 1;
}
else if(1 == N)
{
count++;
return A;
}
}

return A;
}
void main()
{
unsigned int a = 2;
unsigned int N = 0;
unsigned int result = 0;
while(1)
{
count = 0;
printf("\nEnterN:");
scanf("%u",&N);
result = APowerN(a,N);
printf("\ncount:%u\n",count);
printf("\nResult:%u\n",result);
printf("\n**************\n");
}

}

@ sunder ya io think it is optimal :)
approx 0(lgn)

use memoization.

This is near optimal. O(logN)

int power(int a,int n) //n>=0 calculate a^n, for example n=6
{
int count=0,rev_n=0,ret=1;
while(n>0){ //reverse n (n=6 rev_n=3 110->011)
rev_n=(rev_n<<1)+(n&1);
n=n>>1;
count++; //count store how many bits. here count=3
}
while(rev_n>0){ //scan rev_n bits from right
ret=ret*ret*(rev_n&1?a:1);
rev_n =rev_n>>1;
count--;
}
for(;count>0;count--) //rev_n might have fewer bits than n
ret=ret*ret; // 011 needs additional squared calculation
return ret;
}