**Problem**

Given a positive integer n, print the number of ways to convert 2 to n using any following operations:

- Multiply the current number by 2.
- Add 1 to the current number.
- Square the current number.

**Input: **An integer n.

**Output: **Print the number of ways to convert 2 to n.

The questions you should ask the interviewer:

- What is the constraint on n?

**Alert Ninjas:**** Don’t stop now! Enroll in the **__Competitive Programming__** course today. Learn the art of writing time and space-efficient code and compete in code competitions worldwide. **

**Examples:**

- 2 (+1) => 3 (+1) => 4 (+1) => 5 (+1) => 6.
- 2 (+1) => 3 (*2) => 6.
- 2 (*2) => 4 (+1) => 5 (+1) => 6.
- 2 (^2) => 4 (+1) => 5(+1) => 6.
Therefore, the total number of ways is 4.
- 2 +1 => 3 (+1) => 4 (+1) => 5.
- 2 (*2) => 4 (+1) => 5.
*2 (^2) => 4 (+1) => 5.*
Therefore, the total number of ways is 3. |

__Recommended: ____Try to solve it yourself before moving on to____ ____the solution.__

**Solution**

**Idea: **** **The idea is to use __Dynamic Programming__ to count the number of ways required to reach N from 2. As mentioned in the question, we can do the three operations:

- Multiply the current number by 2.
- Add 1 to the current number.
- Square the current number.

Therefore, dp[i+1], dp[i*i], dp[i*2] can be derived from dp[i].

**Algorithm:**

- Initiate a dp array where dp[i] will represent the number of ways to reach i from 2 using the operations mentioned above.
- The base condition will be dp[2] = 1.
- Iterate through the DP array from 2 to N, and use the relation that dp[i] => dp[i+1], dp[i] => dp[i*2], and dp[i] => dp[i*i].
- Similarly, add all the ways to calculate dp[i].
- Return dp[n] as the required answer.

**C++ **

#include <bits/stdc++.h> dp[i+1] += dp[i]; } dp[i*2] += dp[i]; } cin >> n; |

**Input:** n = 6.

**Output: **4

**Input:** n = 5.

**Output: **5

**Time Complexity:** O(N). We used a loop from 2 to N, which will take O(N) time.

**Space Complexity: **O(N). Extra space is used to create the DP array.