3

recently I found an interesting task given in a competition, but without any author solution or explanation how to be solved.

The task consists of the following: The user is given a number N, and has to calculate a^N (on the power of n, not the xor operation), where I can only calculate by multiplying by a, or by a previous result. I should give the smallest number of calculations I should do in order to get calculate a^n.

Example:

N=27
Then the answer is 6:
a^2=a*a
a^3=a^2*a
a^6=a^3*a^3
a^9=a^3*a^6
a^18=a^9*a^9
a^27=a^18*a^9

The limits for N are the following: N<=40000. The time and memory limits are: 2s and 256MB.

What is a good way to solve this task?

Thank you in advance!!!

Ivan Ivanov
  • 243
  • 4
  • 15
  • Maybe a tail recursion? You can find your answer here I think : http://stackoverflow.com/a/26691276 – RicardoVallejo Jun 09 '16 at 01:22
  • 1
    Possible duplicate of [Minimal addition-chain exponentiation](http://stackoverflow.com/questions/7330752/minimal-addition-chain-exponentiation) – Paul Hankin Jun 09 '16 at 01:29
  • @PaulHankin: Agreed, but I think this question does a better job of actually explaining the problem. – j_random_hacker Jun 09 '16 at 10:14
  • Thank you all for the answers! @RicardoVallejo, I am not asking for a fast exponation because in the case of 27 it does not work. PaulHankin and j_random_hacker, thank you for mentioning the common name of that task. From the internet I found out that it is NP-complete, but I could not find a code which works on it, or the idea of the brute force. Can you give me a link, or explain it? Thank you in advance!!! – Ivan Ivanov Jun 09 '16 at 18:22

1 Answers1

0

This is one simple solution but not fast enough.. I wish someone could enhance this by some tweak? Or for someone who is interested just in solving the problem.

#include<set>
#include<iostream>
using namespace std;

int main(int argc, char** argv)
{
    set<int> A, B;
    A.insert(1);
    int n = atoi(argv[1]), i;
    for(i=1; A.find(n) == A.end(); i++) {
        for(auto& a : A) for(auto& b : A) B.insert(a + b);
        for(auto& c : B) A.insert(c);
    }
    cout << i << endl;
}

Let's ask the other way.. How far can I know by calculaing n times? It just doubles every time. Am I missing something? That said, only by this one line,

while(pow(2, n)< atoi(argv[1])) n++;
cout << n;

the result can be gained.

Zeta
  • 913
  • 10
  • 24