how to find the least number of operations to compute x^n

Question

here is the problem from

ACM International Collegiate Programming Contest Asia Regional Contest, Yokohama, 2006-11-05

Starting with x and repeatedly multiplying by x, we can compute x^31 with thirty multiplications:

x^2 = x * x, x^3 = x^2 * x, x^6 = x^3 * x^3, x^7 = x^6 *x, x^14 = x^7 * x^7 ,
x^15 = x^14 * x, x^30 = x^15 * x^15 , x^31 = x^30 * x

write a program to find the least number of operations to compute x^n by multiplication and division starting with x for the given positive integer n and n<=200

for n = 31 the least #operations is 6
for n = 50 the least #operations is 7

Any ideas are welcome.

Answer 1

See this: http://en.wikipedia.org/wiki/Addition-chain_exponentiation

There is no efficient algorithm that will get you the minimum number of steps, and dynamic programming does not work.

I am guessing that n is small enough to allow a brute force solution to pass, although it might need to be optimized. Do you know how to brute force it?

Answer 2

#include<stdio.h>
long long int pow(long long int, long long int);
int count=0;

int main()
{
    long long int a,b;
    printf("Input: ");
    scanf("%lld %lld",&a,&b);
    pow(a,b);
    printf("%d",count);
    return 0;
}

long long int pow(long long int a, long long int b)
{
    count++;
    if(b==0)
    return 1;
    long long int res=pow(a,b/2);
    if(b%2)
    return res*res*a;
    else
    return res*res;
}