Hackerearth The Witches of HEgwarts. What is wrong with my approach?

Question

You can find the problem statement here. My solution can be found here. I am getting correct answers for the test cases but the judge is indicating all answers wrong. What is wrong with my code?

#include <iostream>
#include <vector>
#include <map>
#include <math.h>
using namespace std;

map<long long,long long> arr;
void preProcess();
long long powerOfThree(long long num);
long long powerOfTwo(long long num);
long long theta(long long num);
int main()
{
    preProcess();
    long long t,k;
    cin>>t;
    while(t--)
    {
        cin>>k;
        cout<<theta(k)<<endl;
    }
}

void preProcess()
{
    arr.insert(pair<long long,long long>(0,0));//arr[0]=0;
    arr.insert(pair<long long,long long>(1,0));//arr[1]=0;
    arr.insert(pair<long long,long long>(2,1));//arr[2]=1;
    arr.insert(pair<long long,long long>(3,1));//arr[3]=1;
    //arr.insert(pair<long long,long long>(4,2));//arr[4]=2;
    //arr.insert(pair<long long,long long>(5,3));//arr[5]=3;
}

long long powerOfTwo(long long num)
{
    long long ret=0;
    while(num%2==0)
    {
        ret++;
        num = num/2;
    }
    return ret;
}

long long theta(long long num)
{
    long long ret;
    map<long long,long long>::iterator it = arr.find(num);
    if(it != arr.end())
    {
        return arr[num];
    }
    else
    {
        if(num%2==0)
        {
            long long a = powerOfTwo(num);
            long long q = (num/(long long)pow(2,a));
            ret = a + theta(q);
        }
        else if(num%3==0)
        {
            long long a = powerOfThree(num);
            long long q = (num/(long long)pow(3,a));
            ret = a + theta(q);
        }
        else
        {
            ret = 1 + theta(num-1);
        }
    }
    arr.insert(pair<long long,long long>(num,ret));//arr[num]=ret;
    return ret;
}
long long powerOfThree(long long num)
{
    long long ret=0;
    while(num%3==0)
    {
        ret++;
        num = num/3;
    }
    return ret;
}

My approach is to first count all the powers of 2 and 3 in number and then reduce the result by 1. Again repeat the process till it is 1.

Answer 1

your method will fail in a number say for eg (2^8 + 1) *3^2. There would infact be many such numbers.

I would give a solution in Python(bcoz thats what I am comfortable in):

step = [0,0,1,1]
def find(a):
    global step
    t = len(step)
    for n in range(t,a+1):
        if ((n%3 == 0) and (n%2 == 0)):
            step.append( 1 + min(step[n-1],step[n/2],step[n/3]))
        elif (n%2==0):
            step.append( 1 + min(step[n-1],step[n/2]))
        elif (n%3 == 0) :
            step.append( 1 + min(step[n-1],step[n/3]))
        else :
            step.append( 1 + step[n-1])
    return step[a]

n = int(raw_input())
arr = []
for a in range(0,n):
    arr.append(raw_input())
for st in arr:
    n = int(st)
    print find(n)