int getMinStepsHelper(int n, int steps, int curr, unordered_set<int> &visited, int &minSteps){
	if (curr == n){
        minSteps = steps;
		return steps;
	} else if (curr == 0){
		return INT_MAX; // cannot find a way.
	} else if (steps > minSteps){
        return INT_MAX;
    }

    if (visited.find(curr) != visited.end()){
        return INT_MAX;
    }
    visited.insert(curr);

	return min(getMinStepsHelper(n,steps + 1, curr * 2, visited, minSteps), getMinStepsHelper(n, steps + 1, curr / 3, visited, minSteps));
}

int getMinSteps(int n){
	// only multiply by 2 and divide by 3
	// we cannot reverse the ops and go from n to 0 because div truncates so instead we just start from 1
    unordered_set<int> visited;
    int minSteps = INT_MAX;
	return getMinStepsHelper(n, 0, 1, visited, minSteps);

}

int main(void){
    // exponential time complexity 2^N where N is the depth of the recursion tree i.e. number of min steps
	cout << "min steps is " << getMinSteps(10) <<endl;

}

//1 X 2 X 2 X 2 X 2 / 3 X 2