Number of Ways to Convert 2 into N by Squaring, Adding 1, or Multiplying with 2

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:

1. 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:

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:

1. Initiate a dp array where dp[i] will represent the number of ways to reach i from 2 using the operations mentioned above.
2. The base condition will be dp[2] = 1.
3. 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].
4. Similarly, add all the ways to calculate dp[i].
5. Return dp[n] as the required answer.

C++ 

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.