Consider a directed graph whose vertices are numbered from 1 to n. There is an edge from a vertex i to a vertex j iff either j = i + 1 or j = 3 * i. The task is to find the minimum number of edges in a path in G from vertex 1 to vertex n.
Example 1:
Input:
N = 9
Output:
2
Explanation:
9 -> 3 -> 1, so
number of steps are 2.
​Example 2:
Input:
N = 4
Output:
2
Explanation:
4 -> 3 -> 1, so
number of steps are 2.
Your Task:
You don't need to read input or print anything. Your task is to complete the function minimumStep() which takes the N as inputs and returns the answer.
Expected Time Complexity: O(logN)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{5}

见题面

见题面